SSH "no matching host key type found": cause and fix

What "no matching host key type found" means

Your SSH client and the server couldn't agree on a cryptographic algorithm, so the connection never starts. The usual reason in 2026: your modern client disabled an old, weak algorithm that the old server still relies on. OpenSSH 8.8+ turned off the ssh-rsa (SHA-1) signature by default, and legacy servers, routers, NAS boxes and switches often offer nothing newer. The quick unblock is one flag; the real fix is upgrading the server.

The three variants of this error

All three are the same story — the server only offers algorithms your client has retired for being insecure. The Their offer: part tells you exactly which deprecated algorithm the server is stuck on.

The quick unblock (per connection)

Re-enable the specific old algorithm just for this host. For the most common ssh-rsa case:

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

For an old key-exchange or cipher, the equivalent:

ssh -o KexAlgorithms=+diffie-hellman-group1-sha1 user@host
ssh -o Ciphers=+aes128-cbc user@host

To make it permanent for one host (without weakening security everywhere else), put it in ~/.ssh/config:

Host old-nas
    HostName 192.168.1.10
    HostKeyAlgorithms +ssh-rsa
    PubkeyAcceptedAlgorithms +ssh-rsa

The real fix: upgrade the server

The +ssh-rsa flag is a workaround, not a solution — those algorithms were disabled because they're broken. The durable fix is to make the server offer modern algorithms:

• Update OpenSSH on the server (a current OpenSSH offers Ed25519 and rsa-sha2-256/512 automatically).
• Generate a modern host key if one is missing: sudo ssh-keygen -A regenerates host keys including Ed25519.
• For appliances (old routers, NAS, switches) that can't be updated, the per-host ~/.ssh/config exception is the pragmatic compromise — scope the weak algorithm to just that box.

On a phone

Modern mobile clients negotiate modern algorithms by default — which is good for security but means they hit this same wall against legacy gear. Two things help: prefer Ed25519 keys (TermAI generates them for you), which sidestep the ssh-rsa signature problem entirely on any server that supports them; and for the genuinely old box, a client that lets you set per-connection algorithm options gives you the same escape hatch as ~/.ssh/config.

FAQ

How do I fix "no matching host key type found"?
Add -o HostKeyAlgorithms=+ssh-rsa -o PubkeyAcceptedAlgorithms=+ssh-rsa to the ssh command, or the same lines under a Host block in ~/.ssh/config. Long term, update the server's OpenSSH.

Why did this break after I updated my client?
OpenSSH 8.8+ disabled the legacy ssh-rsa (SHA-1) algorithm by default. Servers that only offer it now fail to negotiate until you re-enable it or upgrade them.

Is re-enabling ssh-rsa safe?
It's weaker than modern algorithms and should be scoped to the specific legacy host that needs it, not enabled globally. The proper fix is upgrading the server.

What's the difference from host key verification failed?
This error is about which algorithms can be used (negotiation). Host key verification failed is about the server's identity key having changed.

Quick Facts

• Meaning: client and server share no acceptable algorithm — usually a modern client vs a legacy server
• Cause: OpenSSH 8.8+ disabled ssh-rsa (SHA-1) and other weak algorithms by default
• Quick unblock: -o HostKeyAlgorithms=+ssh-rsa -o PubkeyAcceptedAlgorithms=+ssh-rsa (scope per host in ~/.ssh/config)
• Real fix: update the server's OpenSSH; regenerate host keys with ssh-keygen -A
• Avoid it: use Ed25519 keys (TermAI generates them) on any server that supports them