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.