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.