After a reboot of our Cisco PIX I was unable to login remotely using ssh. The first thing I tried doing was to remove the the pix entry from my ~/.ssh/known_hosts file. This did not work.

The only way I have found to gain access again is to regenerate the RSA key from the console:

MYPix (config)# ca zeroize rsa
MYPix (config)# ca generate rsa key 1024
MYPix (config)# ca save all

For a Cisco ASA:

MyASA (config)# crypto key generate rsa modulus 2048
MyASA (config)# write memory