How to fix Unable to negotiate with hostname port 22: no matching host key type found. in SSH

First, identify exactly which algorithms the server supports. Run:

ssh -v user@hostname

Look for the line that shows "Their offer:" with a comma-separated list of algorithms. This tells you what the server actually supports. Example output:

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

This shows the server only offers ssh-rsa and ssh-dss, both deprecated algorithms.

If you need to connect immediately, append the -oHostKeyAlgorithms option to your SSH command:

ssh -o HostKeyAlgorithms=+ssh-rsa user@hostname

Or if that doesn't work, try:

ssh -o HostKeyAlgorithms=+ssh-rsa -o PubkeyAcceptedAlgorithms=+ssh-rsa user@hostname

The + prefix means "add this to the default accepted list" rather than replacing it entirely. This is a quick workaround but should only be used temporarily—see the advanced notes for why.

For a more permanent solution without modifying every SSH command, update your SSH client configuration. Edit ~/.ssh/config (create it if it doesn't exist):

Host myserver
    HostName hostname.example.com
    User myusername
    HostKeyAlgorithms +ssh-rsa
    PubkeyAcceptedAlgorithms +ssh-rsa

Replace myserver with an alias, hostname.example.com with the actual server address, and myusername with your username. Then connect using:

ssh myserver

To allow this algorithm for all hosts (less secure, not recommended):

Host *
    HostKeyAlgorithms +ssh-rsa
    PubkeyAcceptedAlgorithms +ssh-rsa

Ensure the SSH config file has restricted permissions:

chmod 600 ~/.ssh/config

Sometimes SSH caches old host key information. Clear the cached entry:

ssh-keygen -R hostname.example.com

Or for an IP address:

ssh-keygen -R 192.168.1.100

This removes the host key from ~/.ssh/known_hosts. On your next connection attempt, you'll be prompted to accept the server's key again. After accepting, retry the connection.

Verify which OpenSSH version is running on your client:

ssh -V

Example output:

OpenSSH_8.9p1 Ubuntu-3ubuntu0.1, OpenSSL 3.0.2 15 Feb 2022

If you're on OpenSSH 8.8 or newer and connecting to older servers, this is expected behavior. The long-term solution is to upgrade the server. For a detailed changelog of what changed, see the official OpenSSH release notes.

The most secure and permanent fix is to update the SSH server to a modern version that supports secure algorithms. The process depends on the server OS:

Ubuntu/Debian:

sudo apt update
sudo apt install -y openssh-server
sudo systemctl restart ssh

CentOS/RHEL:

sudo yum update -y openssh-server openssh-clients
sudo systemctl restart sshd

macOS:

brew install openssh
# Then update your shell's SSH settings

After upgrading, the server will support modern algorithms (rsa-sha2-256, rsa-sha2-512, ecdsa-sha2-nistp256, ed25519) and your client will connect without needing workarounds.