To reduce the impact of private key disclosure, it's advisable to password encrypt the key itself. Offline brute force attacks on specific keys are still possible, but it does throw a wrench in someone who makes off with a cartload of user keys.
Another option -if encryption is not possible- is to restrict the use of the sshkey to specific IP addresses.
Using this syntax in the public key added to the remote server.
from="ipaddress1,ipaddress2" ssh-rsa ...
That means that in the case of somebody stealing those keys, they will be useless if used from any other server (with different IP).
More to the point, you shouldn't store private keys of value on anything you don't control. To connect to a server, storing the public key on the server is sufficient.