TL;DR: ssh -oHostKeyAlgorithms=+ssh-rsa -oRequiredRSASize=1024 <user>@<host>

Have you ever tried to SSH into an old machine, say a managed switch, UPS or router from the previous decade only to get declined with the following error:

Unable to negotiate with <host>: no matching host key type found.
Their offer: ssh-rsa,ssh-dss

It’s frustrating, isn’t it? OpenSSH implements all of the cryptographic algorithms needed for compatibility with standards-compliant SSH implementations, but since some of the older algorithms have been found to be weak, not all of them are enabled by default. If you want to learn more about it, definitely should read OpenSSH Legacy Options .

But this is a tip, so the short story is that you should use one of offered algorithms by the server, say -oHostKeyAlgorithms=+ssh-rsa. When it comes to ssh-rsa, however that won’t be enough and you would be challenged with another error:

Bad server host key: Invalid key length

The crypto-policy that comes with modern distributions does not allow RSA key sizes < 2048 bit. Some SSH servers are configured with 1024-bit key sizes that can lead to connection failures. -oRequiredRSASize=1024 overrides that default and Voilà.