E as perguntas são?
Você está se conectando ao novo sistema (Ubuntu 16.04) de algum cliente SSH muito antigo que não suporta nenhum algoritmo contemporâneo e essa é uma das razões pelas quais ele não consegue se conectar. Você deve realmente atualizar seu cliente.
Ou continue a ativar os protocolos desatualizados que talvez não estejam seguros hoje. Usando
KexAlgorithms +diffie-hellman-group1-sha1
Ciphers +aes128-cbc
você deve conseguir se conectar.