Whenever I tried to connect to some (most) hosts via SSH, I got this error:

1
2

$ ssh username@secretserver.nasa.gov
Unable to negotiate with 69.69.69.69 port 22: no matching host key type found. Their offer: ssh-rsa,ssh-dss

The solution for this is actually very simple. Use your favourite editor (I use VIM) and edit the file located at /etc/ssh/ssh_config. For the sake of time and sanity, use sudo, as it’s a read-only file.

1

$ sudo vi /etc/ssh/ssh_config

At the end of the Host * section add the following line:

HostKeyAlgorithms +ssh-rsa,ssh-dss

Save the file and re-try to connect over SSH.