Update: Actual spookiness

Turns out RSA keys have just been deprecated in open ssh.

The fix was to generate new keys. (ED25519)

It is a pain in the ass to make sure they are properly set up on all my machines now... I have probably missed som places...