If you're using keys for special-purpose accounts, be sure to limit what they can do. You can specify that only a certain command can be run, that port forwarding isn't permitted, etc.
Keys probably don't have to become unmanageable at scale - you can try use SSH certificate authentication.
Sign your keys with a CA, and encode the "principals" that the user has (so, be able to log into some machines as themself, some machines as some other user), and a validity period. Revocation wasn't there yet when last I looked at it (mid-last-year), but might be there now.
One benefit is that individual connections don't need to be brokered by an external authentication/authorisation service. However, it is a relatively new feature and there may be rough edges (such as making sure all your clients have a recent enough version of the tools to work with certificates - Lion was the first MacOS X version to have it, for example).
If you have a larger number, assign them to a group and AllowGroup.
Simple, fast, and effective.
If you can turn off password auth in favor of keys, do that, too.