Tente usar aptitude
em vez de apt-get
:
sudo aptitude install <packagename>
Se você não tem aptidão na sua máquina, pode digitá-la digitando:
sudo apt-get install aptitude
E tente instalar o OpenSSH novamente:
sudo aptitude install openssh-server