Unable to negotiate with 172.22.0.4 port 2222: no matching host key type found. Their offer: ssh-rsa means the server offered only the ssh-rsa host key signature, and this OpenSSH client does not accept it by default. In this test, allowing it for that one server with HostKeyAlgorithms +ssh-rsa in a Host entry of ~/.ssh/config fixed it.

In the same test, the same container's default sshd on port 22, which offered an ED25519 host key, accepted the same client without any change. Only the per-host setting was tested as a fix for the port 2222 server.

The error

$ ssh -o BatchMode=yes -p 2222 dev@sshd hostname
Unable to negotiate with 172.22.0.4 port 2222: no matching host key type found. Their offer: ssh-rsa
exit=255

Why it happens

The test server ran a second sshd on port 2222, started with only its RSA host key and restricted to the ssh-rsa algorithm: 

/usr/sbin/sshd -p 2222 -h /etc/ssh/ssh_host_rsa_key -o HostKeyAlgorithms=ssh-rsa

The client, OpenSSH_9.6p1, refused to agree on that algorithm and stopped with exit code 255 before any login. The RSA key file itself worked: the legacy login on port 2222 below, with HostKeyAlgorithms +ssh-rsa, went through with that same key, so the problem was the algorithm the client would accept. The message names the address and port it talked to and, after Their offer:, the list of host key types the server sent; here that list had one entry.

The fix

$ cat /root/.ssh/config
Host sshd
    User dev

Host legacy
    HostName sshd
    Port 2222
    User dev
    HostKeyAlgorithms +ssh-rsa
exit=0
$ ssh-keyscan -p 2222 -t rsa sshd 2>/dev/null | ssh-keygen -lf -
3072 SHA256:eJ2IN0oCE3Sti2gCZLj4arNfUJDBkJPTYnTYcNfomHU [sshd]:2222 (RSA)
exit=0
$ ssh -o BatchMode=yes -o StrictHostKeyChecking=accept-new legacy hostname
9aec0d80cdf9
exit=0
$ ssh -o BatchMode=yes sshd hostname
9aec0d80cdf9
exit=0

The Host legacy entry points at the same server and port and adds ssh-rsa to the accepted host key algorithms for that entry only. The fingerprint from ssh-keyscan matched the one the server printed for its RSA key (ssh-keygen -lf /etc/ssh/ssh_host_rsa_key.pub) before the key was accepted with accept-new. The connection to sshd on port 22, which has no such line, kept working. The test went no further than this one server; nothing here says how any real server is set up.

How it was reproduced

Reproduced inside ubuntu:24.04 containers on one user-defined Docker network on Docker engine 29.9.3, with OpenSSH_9.6p1 Ubuntu-3ubuntu13.20 as client and server. The server container ran its default sshd on 22 and the restricted one on 2222, with a test user dev holding the client's Ed25519 public key. The containers and the network were removed afterwards.

Frequently asked

How do I fix no matching host key type found. Their offer: ssh-rsa?
For that one server, add a Host entry in ~/.ssh/config with HostKeyAlgorithms +ssh-rsa. In this test that let OpenSSH 9.6p1 connect while other hosts kept the defaults.
Why does SSH refuse ssh-rsa host keys?
In this test the OpenSSH 9.6p1 client refused a server that offered only the ssh-rsa algorithm, while the same server's default sshd on port 22 worked.
Should I enable ssh-rsa for all hosts?
This test enabled it for one Host entry only and left every other host on the defaults. The same container's sshd on port 22, offering an ED25519 host key, accepted the client without any change.

For a host key that changed rather than one of an old type, see SSH: Remote host identification has changed. More decoded errors in the Fixes category.