You could probably do a hack to let the user login with ssh key and then immediately force the second factor auth to be run, booting the user out if they didn't pass it. Not the best way, but one option.
I also believe I once ran across a patch someone had done to the login code to allow both to be required, I can't find the link right off though as I'm at work currently. If I find it, I'll add it here
Yes, I have seen a patch as well that allowed you to require both an ssh key and a password ... it was an old patch, though, and I can't imagine it would apply cleanly to any recent OpenSSH ...
This is on our list to pay for someone to do, and we'll release it when they do ... it will probably be FreeBSD-centric, but if it's against OpenSSH generally, it should be usable by others...
I also believe I once ran across a patch someone had done to the login code to allow both to be required, I can't find the link right off though as I'm at work currently. If I find it, I'll add it here