Esta postagem resolveu meu problema. Foi por causa dos seguintes arquivos:
/usr/bin/ssh
/usr/sbin/sshd
que estavam impedindo aptitude
de atualizar corretamente openssh-server
.
Depois de seguir as instruções no post mencionado, acabei de fazer:
$ sudo aptitude reinstall openssh-server ssh
E o problema foi resolvido!