How to fix no hostkey alg in SSH

Run verbose SSH and look for the host key algorithm negotiation lines:

ssh -vvv user@hostname 2>&1 | grep -i "host key algorithms"

This surfaces the real debug line, debug2: host key algorithms:, showing the algorithms the client is willing to accept. You can also list everything your client supports independently of any connection:

ssh -Q HostKeyAlgorithms

Compare these against what the server actually offers to find the specific mismatch.

If the server only has an RSA host key, you can re-enable ssh-rsa for that connection. On OpenSSH 8.8+ you must allow it for both host key verification and public-key authentication:

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

The PubkeyAcceptedAlgorithms option is required because 8.8+ also disables ssh-rsa for key-based auth, so omitting it can leave authentication failing even after the host key is accepted.

Or add it to ~/.ssh/config for persistent use:

Host specific-server
    Hostname 192.168.1.100
    User myuser
    HostKeyAlgorithms +ssh-rsa
    PubkeyAcceptedAlgorithms +ssh-rsa

The + prefix appends to the defaults instead of replacing them. This re-enables a deprecated SHA-1 algorithm, so treat it as a temporary measure only and prefer fixing the server.

Edit /etc/ssh/sshd_config and set HostKeyAlgorithms to modern options:

# Add strong modern algorithms
HostKeyAlgorithms ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ecdsa-sha2-nistp256

Then restart sshd:

sudo systemctl restart sshd
# or on some systems:
sudo service sshd restart

This keeps security intact while supporting modern clients. ssh-ed25519 and the rsa-sha2-* variants use secure hash algorithms.

Check which host keys exist:

ls -la /etc/ssh/ssh_host_*

If the ed25519 or ecdsa keys are missing, generate them so the server can offer a non-SHA-1 host key:

sudo ssh-keygen -t ed25519 -f /etc/ssh/ssh_host_ed25519_key -N ""
sudo ssh-keygen -t ecdsa -f /etc/ssh/ssh_host_ecdsa_key -N ""
sudo systemctl restart sshd

Modern clients prefer ed25519 for both security and performance, which permanently resolves the mismatch without any client-side workaround.

Check your SSH version:

ssh -V

If you are on a very old OpenSSH (< 6.5) connecting to a modern server, update the client:

# Ubuntu/Debian
sudo apt-get update && sudo apt-get install openssh-client

# macOS (via Homebrew)
brew install openssh

# CentOS/RHEL
sudo yum update openssh-clients

Older clients lack support for modern algorithms, so upgrading resolves this permanently.