Comment 6 for bug 1961833

For reference to anyone coming here with this problem, when connecting to a remote sshd server you can find what host key algorithms the remote host uses by using -vv and check the debug output; look first for the *peer* server KEXINIT proposal (not the earlier *local client* KEXINIT proposal):

debug2: peer server KEXINIT proposal

a line or two after that, you should see the list of host key algorithms the remote host is offering; if it contains *only* ssh-rsa then this bug is relevant.

debug2: host key algorithms: ssh-rsa

Note that by default many systems support multiple algorithms, e.g. you may see:

debug2: host key algorithms: ssh-rsa,ssh-dss,ecdsa-sha2-nistp256,ssh-ed25519

in this case, even though the remote host does offer ssh-rsa, it also supports other algorithms that jammy does support.