Best way to setup sudo authentication on servers that don’t use a password

Sudo, in its most common configuration, requires the user to type their password. Typically, the user already used their password to authenticate into the account, and typing the password again is a way to confirm that the legitimate user hasn't abandoned their console and been hijacked.

In your setup, the user's password would be used only for authentication to sudo. In particular, if a user's SSH key is compromised, the attacker would not be able to elevate to root privileges on the server. The attacker could plant a key logger into the account, but this key logger would be detectable by other users, and could even be watched for automatically.

A user normally needs to know their current password to change it to a different password. The passwd program verifies this (it can be configured not to, but this is not useful or at all desirable in your scenario). However, root can change any user's password without knowing the old one; hence a user with sudo powers can change his own password without entering it at the passwd prompt by running sudo passwd $USER. If sudo is configured to require the user's password, then the user must have typed the password to sudo anyway.

You can disable password authentication selectively. In your situation, you would disable password authentication in ssh, and possibly in other services. Most services on most modern unices (including Ubuntu) use PAM to configure authentication methods. On Ubuntu, the PAM configuration files live in /etc/pam.d. To disable password authentication, comment out the auth … pam_unix.so line in /etc/pam.d/common-auth. Furthermore, make sure you have PasswordAuthentication no in /etc/ssh/sshd_config to disable sshd's built-in password authentication.

You may want to allow some administrative users to log in with a password, or to allow password authentication on the console. This is possible with PAM (it's pretty flexible), but I couldn't tell you how off the top of my head; ask a separate question if you need help.

1. A key pair is not tied to you as a user or your machine. Imagine having the keys to your house stolen. The keys aren't bound to you, anyone can use them to unlock your doors. In the exact same way, if I get my hands on your private key, I can use it to make changes to your Github repositories.
2. If you wish to access your repositories using both your new keys and your old ones, you need to make sure the public keys for both key pairs are uploaded to Github. If Github only has your new key, it cannot authenticate you if you use your old key pair.
3. Yes, the keys will change. That's sort of the point. Imagine buying a new lock for your door. If your old keys are the same as your new ones, it won't do you any good, esp. if you were changing the lock because someone stole your old key. If you were to have one of your ssh keys compromised, you could simply generate new keys & upload the corresponding public keys to Github after deleting the old ones. You can also have multiple key pairs. Generate as many as you wish and use them for different purposes. This is similar to having multiple keys for multiple locks in your house.

Also NEVER EVER give away your private keys. The private key is what is used to authenticate you as a person. If I get my hands on your private key, I can fake being you. Github can't tell the difference. No one but you needs to know what your private key is. If you have uploaded your private key somewhere, I recommend deleting it, generating a new pair & uploading the new public key just to be safe.

Read more about public key cryptography here.