Fixing SSH "no hostkey alg" on Debian/Ubuntu

If SSH to a Debian/Ubuntu server returns “no hostkey alg”: the SSH client has failed the host key algorithm check while attempting to connect. Steps to fix it: Check the permissions of files beginning with ssh_host_ in /etc/ssh using:

ls -l /etc/ssh/ssh_host_*

If the permissions are not 600 (-r-x------), change them with:

sudo chmod 0600 /etc/ssh/ssh_host_*

If all permissions are correct but “no hostkey alg” persists, add key algorithms to /etc/ssh/sshd_config using:

sudo nano /etc/ssh/sshd_config

Add the key algorithms:

HostKeyAlgorithms +ssh-rsa,ssh-dss

Then restart the SSH server.

sudo systemctl restart ssh