If you're that concerned about security, there are a handful of additional things you can do:
* Use a non-standard ssh port
* Disable root ssh login
* Configure 'Single Packet Authorization and Port Knocking' -- http://www.cipherdyne.org/fwknop/
* Have decent iptables rules. Use either fail2ban or denyhosts with stringent rules, if you must, that ban on 3+ failed logins.
* Have a whitelist of acceptable IP's for ssh access
* Use any system of 2-factor authentication. I'm partial to Google's Authenticator. Here're some directions to get that set up, if anyone is interested: http://guides.webbynode.com/articles/security/ubuntu-google-...
But seriously, if you have keys set up and someone manages to steal them... you've really got bigger things you should be focusing on.