Example error message:

Unable to negotiate with my.host.example.com port 22: no matching host key type found. Their offer: ssh-rsa,ssh-dss

Solution:

We can fix that for this host by adding the following example to our SSH config:

Host my.host.example.com
  HostKeyAlgorithms ssh-rsa
  PubkeyAcceptedKeyTypes ssh-rsa

Adjust the example text to fit your situation. When SSH is used to connect to that specific host on any port, we now specifically allow ssh-rsa as a key type.

Our personal SSH config is in ~/.ssh/config, when working on Linux or macOS. We can also add this to the system-wide config that will be used with any user, but that requires root privileges.

Context:

This message can occur when using openssh or anything that uses openssh to connect, like using lftp to connect to sftp addresses. The port on that server would like to talk to you, but your client is communicating that it wants to work with key types other than those the certificate on the server is using.

If this happened suddenly then it is possible that an openssh update has been applied where the default behaviour has changed. Perhaps the key type in question is seen as less secure today than it was in the past. It is also possible that a change occurred on the server.