Is it possible and feasible to setup a linux box to first require a valid key file before prompting for the user's local account credentials? Our setup is that we have to open ssh on a machine to the internet but there's only like 2 people who would need to ssh into it. We want to lock this bad boy down as tight as possible. We are already implementing the usual, firewall, denyhosts, etc, but if this is possible, I'd like to throw it in as well. All replies are appreciated!
If your SSH keys already have a pass phrase (which they should) then you're already doing two-factor, and IMO, adding the local account password to that process isn't going to give you much besides annoyed users.
If your intent is to allow only those two users to login via SSH, you can use the AllowGroups and/or AllowUsers configuration features in your sshd_config.
Check the man page for sshd_config to see what options are available. HostBasedAuthentication looks promising.
If you can't find what you need, (and even if you can) you could lock down what can be done on the machine, by requiring the use of sudo for many functions - that can be configured to require a password, log everything that gets done, and IMHO should be set up at least as default on any Linux server you use.
See the man page for sudo and sudoers, of course, but also a nice discussion on my favourite page on securing linux servers