How to fix an ssh connection refused with "no hostkey alg"

If connecting to a server over SSH fails with “no hostkey alg”, as shown below:

debug1: Reading configuration data /etc/ssh_config
debug1: Connecting to 192.168.1.1 [192.168.1.1] port 22.
debug1: Connection established.
debug1: identity file /home/tum/.ssh/identity type -1
debug1: identity file /home/tum/.ssh/id_rsa type 1
debug1: identity file /home/tum/.ssh/id_dsa type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.2
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.3
debug1: match: OpenSSH_5.3 pat OpenSSH_5*
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
no hostkey alg

To fix this, generate RSA and DSA keys with these commands.

# ssh-keygen -t rsa -f /etc/ssh/ssh_host_rsa_key
# ssh-keygen -t dsa -f /etc/ssh/ssh_host_dsa_key

For newer Debian/Ubuntu versions Fixing SSH “no hostkey alg” on Debian/Ubuntu