How do I setup sshd to require both a private key and a password?

You need to setup an SSH gatekeeper. This allows openssh to permit multifactor authentication.

Here's a great link: https://calomel.org/openssh.html

Essentially, you use the ForceCommand directive to run a script when the user logs in. That script then prompts the user for the password. I'm currently looking for a method to verify a given password against the system password, but I'm coming up (understandably) blank.

If the user account is stored in an LDAP directory, you could attempt to bind to the directory using those credentials, but the problem is going to be that the program running will be running as the user, not as root. I don't know the security implications of writing the compiled code and setting it SUID.

Hopefully someone will give you a better answer.

but since I've typed this much, are you in an ultra-secure site? Because that's really the only reason for this. Normal public keys with passphrases should be more than adequate for 99% of cases out there.

Recent versions of OpenSSH have made this much easier to accomplish!

In /etc/ssh/sshd_config simply add the following:

AuthenticationMethods "publickey,password" "publickey,keyboard-interactive"

If you wish to allow a specific IP address (e.g. 192.168.10.10) to be able to log in with the OpenSSH default methods, but require every other IP address to use both a password and key, you can add the following Match block instead:

Match Address "*,!192.168.10.10"
    AuthenticationMethods "publickey,password" "publickey,keyboard-interactive"

Though not well documented, the leading asterisk is required on the match line; Match Address "!192.168.10.10" will actually never match. This may change in future versions of OpenSSH.