The solution is to add the following line to ~/.ssh/config on every client machine (every machine where you run the SSH client): PubkeyAcceptedKeyTypes=+ssh-dss If the server is using OpenSSH 7.0 or newer, you’ll also need to add this line to /etc/ssh/sshd_config on each server machine.