The big problem with ssh keys is not being able to enforce ssh key passphrases on users. From the server perspective, you have no idea if the user has set up a passphrase. There are security standards which mandate certain kinds of passwords (complexity) and are silent on asymmetric keys, so you couldn't use keys in those environments.
The old solution was to do some post-login hack to require a password as well (e.g. to su), or do a VPN (which could have multiple forms of auth) and then ssh with keys after that, but the newest ssh (and I believe commercial ssh for a long time) now supports requiring multiple authentications per login, so you can do ssh key plus passphrase.
There are also DLP/etc. reasons why ssh can be problematic in some environments (i.e. where you're required to log/analyze actions taken by users, particularly admin users). The solution there is to use a bastion host and ssh in and then ssh out, with the user account locked down to log. SSH Communications (the commercial ssh people) have an interesting ssh MITM box which essentially does what all the SSL x509 MITM CA things do.
Expiring an ssh-key is easy, just remove the public key from authorized_keys. Dealing with theft is also straightforward: just add a passphrase to the key -- the time it takes to crack your pass phrase should be more than the time it takes for you to run ssh-keygen && ssh-copy-id.
Expiring an ssh-key on YOUR machine is "easy". Ensuring it's really gone on every, single UNIX-like box anywhere in your company is less easy. Oh, and what happens when you restore a home directory or entire machine from tape? Are you absolutely sure you remembered to delete every SSH key you wanted to "expire" at some point?
SSH keys do not satisfy a "fail closed" security model: they're there unless you explicitly remove them (and keep them removed). Certificates, tickets, and other expiring credentials eventually go away and lock users out unless they're explicitly renewed.
The issue is lack of key management for ssh keys in a lot of environments, especially for accounts not always used. You can wrap protection around it, but you ay be better off just using a different authentication system (Kerberos? Something else?) in large environments.
> There are security standards which mandate certain kinds of passwords (complexity) and are silent on asymmetric keys, so you couldn't use keys in those environments.
Every single auditor I've worked with has given a pass when they saw we were using keys instead of passwords. Do you also fail audits because your RSA token is only 10-12 digits?
You could, I suppose, demand users upload their private key (shudder) to the organization so you can check if it's encrypted; this has its own flaws (primarily that you've just taught your users to be giving with their private key), and you still can't enforce passphrase strength well.
Yes -- FISMA. There are both requirements that the implementations be FIPS 140 (although software is ok) and other requirements. I don't think I've ever seen anyone use a securid without a password, so the password complexity requirement is satisfied there. (It wasn't that an auditor failed it, but it was said we'd need to fix this to avoid any issues, so enh)
I don't have a particularly high opinion of most security audit standards, though.