There are a lot of open issues with ssh keys, especially in an internal environment with a lot of end users. Is is difficult to control the distribution of keys or force a key password policy.

1) Users will copy their .ssh directories to every server they have access to so that they don't have to type in passwords. To deal with this:

  a. You can limit where public keys are stored with the AuthorizedKeysFile directive in sshd_conf. Force all keys to be controlled by root and in a central location. 

  b. Implement kerberos so that users don't need to use keys for single sign-on.

  c. only allow keys for functional ids (i.e. mysql), use IP filtering (from=xxx.xxx.xxx.xxx) on the public key to limit key access to a few administrative servers. 

  d. If NFS homedirs are exported to the world, any attacker can mount them and read off the keys from .ssh directories.

Other folks have mentioned brute-force attacks against your ssh daemons on the public internet. If possible, you should think about using a VPN/two-factor authentication to get access to your network or internal gateway servers.