How to fix SSH no matching host key type found

Newer OpenSSH clients can stop before login when an older server offers only the ssh-rsa host key signature. The no matching host key type found error is a negotiation failure, not a password, private-key, or known_hosts problem. Fix it by allowing the legacy host key algorithm only for the affected host while the server is upgraded to offer Ed25519, ECDSA, or RSA SHA-2 host keys.

HostKeyAlgorithms controls the server host key algorithms accepted by the client. A value that starts with + appends a legacy name to the client default instead of replacing modern defaults. A Host-specific block in ~/.ssh/config keeps the exception tied to one alias and avoids weakening every SSH connection from the client.

Treat ssh-rsa as a temporary compatibility exception because it uses RSA with SHA-1 signatures. If the connection later fails during public-key authentication with a mutual signature error, the same server may also need PubkeyAcceptedAlgorithms +ssh-rsa in the same Host block, but the better fix is to update the server firmware or sshd host keys.

1. Run the failing SSH command and read the offered host key type.

   $ ssh admin@legacy-appliance hostname
   Unable to negotiate with legacy-appliance port 22: no matching host key type found. Their offer: ssh-rsa

   The value after Their offer is the algorithm name to scope in the client exception. Do not treat this as a changed-key warning from known_hosts.

2. Test a one-command exception for the affected host key algorithm.

   $ ssh -o HostKeyAlgorithms=+ssh-rsa admin@legacy-appliance hostname
   legacy-appliance

   Use this as a diagnosis step, not as a shell alias or global option. The leading + keeps modern defaults and appends ssh-rsa only for this command.

3. Open the per-user OpenSSH client configuration file.

   $ nano ~/.ssh/config

   Use the user config instead of /etc/ssh/ssh_config unless the exception is intentionally managed for every account on the client.

4. Add a narrow Host block for the legacy server.

   Host legacy-appliance
       HostName legacy-appliance.example.net
       User admin
       HostKeyAlgorithms +ssh-rsa

   Add PubkeyAcceptedAlgorithms +ssh-rsa in this same Host block only if the host key error is gone and public-key authentication later reports no mutual signature algorithm.

5. Check the effective client configuration for the alias.

   $ ssh -T -G legacy-appliance
   host legacy-appliance
   user admin
   hostname legacy-appliance.example.net
   port 22
   ##### snipped #####
   hostkeyalgorithms ssh-ed25519-cert-v01@openssh.com,ecdsa-sha2-nistp256-cert-v01@openssh.com,ecdsa-sha2-nistp384-cert-v01@openssh.com,ecdsa-sha2-nistp521-cert-v01@openssh.com,sk-ssh-ed25519-cert-v01@openssh.com,sk-ecdsa-sha2-nistp256-cert-v01@openssh.com,rsa-sha2-512-cert-v01@openssh.com,rsa-sha2-256-cert-v01@openssh.com,ssh-ed25519,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,sk-ssh-ed25519@openssh.com,sk-ecdsa-sha2-nistp256@openssh.com,rsa-sha2-512,rsa-sha2-256,ssh-rsa
   ##### snipped #####

   ssh -G prints the resolved client settings and exits before authentication. The hostkeyalgorithms line should still contain modern names before the appended ssh-rsa fallback.
   Related: How to show SSH client configuration

6. Connect through the saved alias.

   $ ssh legacy-appliance hostname
   legacy-appliance

   Accept a new RSA host key only after its fingerprint matches a trusted source. The algorithm exception does not verify that the server identity is safe.

7. Remove the exception after the server offers modern host key algorithms.

   $ ssh -o HostKeyAlgorithms=-ssh-rsa legacy-appliance hostname
   legacy-appliance

   If this test succeeds, remove HostKeyAlgorithms +ssh-rsa from the Host block. If the same host key error returns, leave the per-host exception in place and schedule the server-side host key or firmware upgrade.
   Related: How to regenerate SSH host keys