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!