Não é um acidente. Apenas falha ao iniciar devido à opção errada de configuração:
Apr 17 12:34:14 hn0-hdi-us sshd[1437]: /etc/ssh/sshd_config: line 20: Bad configuration option: KexDHMin
A opção ServerKeyBits
também está obsoleta no OpenSSH atual. Eu não acho que esta opção está lá enviada por padrão Ubuntu, basta removê-lo. Não é útil para nada (a menos que você use o protocolo SSH-1 por algum motivo, mas nesse caso você já está ferrado).