userauth_pubkey: key type ssh-dss not in PubkeyAcceptedKeyTypes [preauth]

Se você acabou de atualizar o Ubuntu para as versões 16 ou 18, pode ser que você obtenha um erro de conexão em função da nova forma de operação do OpenSSH.
O OpenSSH quando mudou da versão v6.9 para a v7.0 recusa conexões de ssh devido a alterações no formato do arquivo de configuração.

No meu caso o seguinte erro aparecia no arquivo /var/log/auth.log do computador que eu queria conectar

sshd[6850]: userauth_pubkey: key type ssh-dss not in PubkeyAcceptedKeyTypes [preauth]
sshd[6850]: error: maximum authentication attempts exceeded for root from x.x.x.x port 51702 ssh2 [preauth]
sshd[6850]: Disconnecting authenticating user root x.x.x.x port 51702: Too many authentication failures [preauth]

Para resolver este erro foi preciso editar o arquivo /etc/sshd_config e acrescentar a seguinte linha no final do arquivo de configuração:

PubkeyAcceptedKeyTypes=+ssh-dss

Agora foi só reiniciar o ssh usando service ssh restart, e a conexão passou a ser reconhecida.
Esta configuração vale para todos os usuários.
Você pode acrescentar esta linha em  ~/.ssh/config para o usuário local.