Olhando mais cedo, acabei de ver isto:
Jun 25 10:46:44 dmz sshd[29221]: debug1: Server will not fork when running in debugging mode.
... o que parece bastante suspeito.
Verificando os processos que vejo:
/etc/sbin/sshd -D -d
Verificando o / etc / default / ssh eu vejo:
SSHD_OPTS="-d"
que eu comentei.
Eu não sei porque foi definido, eu não me lembro de configurá-lo e o ssh funcionou bem até que eu atualizei 14: 04LTS para 16: 04LTS.
ssh agora funciona como esperado.