Running debsums indicates that some files have different checksum from the files provided by the debian packages.
$ debsums -s
indicates that libk5crypto.so.3.1 and libcrypto.so.1.0.0 (and a few more) have status FAILED.
You will want to replace these files with files provided by the debian packages. To find out what package owns a file:
$ dpkg --search /usr/lib/x86_64-linux-gnu/libk5crypto.so.3.1
This tells us that this file is provided by libk5crypto3. (running the command with libcrypto.so.1.0.0 tells us that it is provided by the libssl1.0.0 package)
Then, simply reinstall the package(s):
$ sudo apt-get --reinstall install libk5crypto3 libssl1.0.0
Then, attempt to reinstall openssh:
$ sudo apt-get purge openssh-server $ sudo apt-get install openssh-server