A versão do OpenSSH incluída no 16.04 desabilita o ssh-dss. Há uma página simples com informações herdadas que incluem esse problema: link
Em poucas palavras, você deve adicionar a opção -oHostKeyAlgorithms=+ssh-dss ao comando SSH:
ssh -oHostKeyAlgorithms=+ssh-dss [email protected]
Você também pode adicionar um padrão de host em ~/.ssh/config , para não precisar especificar o algoritmo de chave sempre:
Host nas
HostName 192.168.8.109
HostKeyAlgorithms=+ssh-dss
Isso traz o benefício adicional de que você não precisa digitar o endereço IP. Em vez disso, ssh reconhecerá o host nas e saberá onde se conectar. Claro que você pode usar qualquer outro nome em seu lugar.