Pode ser um problema de hardware intermitente no seu novo servidor. Cabo defeituoso? NIC Esta máquina estava anteriormente funcionando corretamente 14.04?
Como você pode se conectar bem a outras máquinas, se o problema não for hardware, talvez você deva dar uma olhada na configuração do daemon ssh na nova caixa 16.04, vim /etc/ssh/sshd_config
O que você já tentou para resolver isso?
Você pode executar o sshd com opções de depuração na caixa 16.04:
"... o modo de depuração fornece muitas informações sobre a conexão e uma quantidade menor sobre a configuração do servidor. O nível de depuração do servidor (- d ) pode ser aumentado uma vez, duas vezes (- dd ) ou três vezes (- ddd ). "
No seu terminal, você pode executar o cliente ssh com a opção -vvv também.
ssh -p 22 -vvv <user>@<server>