Comment 7 for bug 230174

Per Chris K. Jester-Young's suggestion, I downloaded and manually installed:
libssl0.9.8_0.9.8e-5ubuntu3.2_i386.deb
That resolved the problem and I now show:

====
$ sudo apt-get install ssh
[sudo] password for:
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages were automatically installed and are no longer required:
  openoffice.org-writer libneon27 openoffice.org-impress libicu38
  openoffice.org-draw libhal-storage-dev openoffice.org-math libhal-dev
  libldap-2.4-2 libdb4.6 openoffice.org-calc
Use 'apt-get autoremove' to remove them.
The following extra packages will be installed:
  openssh-blacklist openssh-client openssh-server
Suggested packages:
  ssh-askpass libpam-ssh keychain rssh molly-guard
The following NEW packages will be installed:
  openssh-blacklist openssh-client openssh-server ssh
0 upgraded, 4 newly installed, 0 to remove and 6 not upgraded.
Need to get 0B/3080kB of archives.
After unpacking 6672kB of additional disk space will be used.
Do you want to continue [Y/n]? y
Preconfiguring packages ...
Selecting previously deselected package openssh-client.
(Reading database ... 291500 files and directories currently installed.)
Unpacking openssh-client (from .../openssh-client_1%3a4.6p1-5ubuntu0.5_i386.deb) ...
Selecting previously deselected package openssh-blacklist.
Unpacking openssh-blacklist (from .../openssh-blacklist_0.1-1ubuntu0.7.10.1_all.deb) ...
Selecting previously deselected package openssh-server.
Unpacking openssh-server (from .../openssh-server_1%3a4.6p1-5ubuntu0.5_i386.deb) ...
Selecting previously deselected package ssh.
Unpacking ssh (from .../ssh_1%3a4.6p1-5ubuntu0.5_all.deb) ...
Setting up openssh-client (1:4.6p1-5ubuntu0.5) ...

Setting up openssh-blacklist (0.1-1ubuntu0.7.10.1) ...
Setting up openssh-server (1:4.6p1-5ubuntu0.5) ...
Creating SSH2 RSA key; this may take some time ...
Creating SSH2 DSA key; this may take some time ...
 * Restarting OpenBSD Secure Shell server sshd [ OK ]

Setting up ssh (1:4.6p1-5ubuntu0.5) ...

$ sudo ssh-vulnkey -a
Not blacklisted: 2048 90:f3:b6:29:cd:57:ef:1d:2e:af:1a:26:87:ec:5b:17 /etc/ssh/ssh_host_rsa_key.pub
Not blacklisted: 1024 ca:ff:17:ee:f9:6a:d1:32:a9:85:2b:af:70:80:bd:ce /etc/ssh/ssh_host_dsa_key.pub
====

Thank you Chris!