Ubuntu Security :: Replacing A Possibly Compromised OpenSSH Key?

I have an OpenSSH server running on Ubuntu 10.04, and it works fine.

I'm concerned that my SSH key may have been compromised and would like to replace it.

I tried replacing keys before and reinstalling OpenSSH and SSH before but ran into terrible trouble so I'm asking for instruction before touching anything this time.

Code:
laeg@skyrocket:~/.ssh$ ls
authorized_keys id_rsa id_rsa.ppk id_rsa.pub known_hosts
Code:
laeg@skyrocket:/etc/ssh$ ls

[Code]....

So can I just synpaptic 'fully' uninstall SHH (although probably even less necessary than..) and OpenSHH, backup sshd_config, delete the two dirs referenced above, reinstall both packages, insert my sshd_config backup, and then start from scratch following the guides linked below?