Debian / Ubuntu Linux Public key Blacklisted (see ssh-vulnkey(1)) Error and Solution

Q. When ever I try to login to my remote Debian Linux server called in013.example.com, I get the following error message in /var/log/auth.log file:

Jul 1 17:04:36 in013 sshd[14447]: Public key 48:de:55:22:xx:yy:zz:yy:xx:yy:zz:yy::88:e8:87:47 blacklisted (see ssh-vulnkey(1))
Jul 1 17:04:36 in013 sshd[14447]: Public key 48:de:55:22:xx:yy:zz:yy:xx:yy:zz:yy::88:e8:87:47 blacklisted (see ssh-vulnkey(1))

I'm using Ubuntu Linux as desktop operating system. How do I fix this error?

A. This is well known security flow in Debian / Ubuntu Linux OpenSSL package. First, you need to update your Ubuntu Linux desktop software, by typing following commands:
$ sudo apt-get update
$ sudo apt-get upgrade
This will update openssl, openssh server and client packages for you. This will also regenerate COMPROMISED keys stored /etc/ssh/ directory. However, this will update your personal COMPROMISED keys stored at $HOME/.ssh. Type the following command to list all COMPROMISED keys:
$ sudo ssh-vulnkey -a
ssh-vulnkey checks a key against a blacklist of compromised keys. You must remove all COMPROMISED keys and regenerate them again using ssh-keygen command.
$ cd ~/.ssh
$ rm id_*
$ ssh-keygen -t rsa
OR
ssh-keygen -t dsa
Upload new id_rsa.pub or id_dsa.pub file to remote host and overwrite existing authorized_keys2 file, enter:
$ scp ~/.ssh/id_rsa.pub user@in013.example.com:.ssh/authorized_keys2
If you have multiple keys, then copy ~/.ssh/id_rsa.pub to $HOME and manually delete / update authorized_keys2 file:
$ scp ~/.ssh/id_rsa.pub user@in013.example.com:~/
Find out line number, enter:
$ grep 'your-desktop-name' ~/.ssh/authorized_keys2
Use vi to open COMPROMISED key, enter (replace N with actual line number):
$ vi +N ~/.ssh/authorized_keys2
Delete file pressing dd once. Save and close the file. Append new public key, enter:
$ cat ~/id_rsa.pub >> ~/.ssh/authorized_keys2

Suggested readings:

• Impact of the Debian OpenSSL Vulnerability On other Linux Distribution
• Ubuntu / Debian Linux Regenerate OpenSSH Host Keys
• man pages ssh-keygen, ssh-vulnkey,scp, and ssh