Este erro ocorre quando os computadores com clientes ssh atuais tentam se conectar com servidores que utilizam encriptação antiga ssh-dss. Este tipo de encriptação além de depreciada, não é utilizado nos clientes ssh atuais. A seguir, a solução editando o arquivo config presente na pasta ~/.ssh para força este tipo de encriptação.

Host meuservidor
         Port 22
         Hostname meuservidor
         User cabelo
         HostKeyAlgorithms ssh-dss
         PubkeyAcceptedKeyTypes ssh-dss
Exemplo do erro ao tentar se conectar com servidores antigos.