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.
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.
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.
