It seems like using a username and password for SSH would be more convenient because it can be typed whereas a private key needs to be stored on every computer you use for SSH.
Therefore if you want the ability to SSH into a server from any computer you should stick with username and password.
Is this premise correct?
No, because if SSH does not find a valid key, it will fall back to password anyway. Therefore you lose nothing by having keys set up for your main machines.
whereas a private key needs to be stored on every computer you use for SSH.
This is not a correct way to use SSH. Copying the private key between computers is a weak point that can/should be avoided. The correct way is to generate a keypair at each computer and add all of the public keys to the authorized keys file. You can copy a new public key to another computer you already have access from, and use ssh to update the authorized keys file with the new public key.
Therefore if you want the ability to SSH into a server from any computer you should stick with username and password.
This is kind of true, but your security will suck because you're starting from the premise that you want to access your account from "any computer" (which may have a rootkit, keylogger and/or fake ssh installed).
I am just trying to see if I am missing something here
Something that you may take into account is that usually, as a sysadmin, you will have your own workstation and, in this workstation, you will have your user profile with your identity (i.e. your private key). And, if you are using several workstations, ideally, your user environment files will be replicated. Also, if for any reason you cannot be in front of your workstation, you will SSH your workstation with your credentials and, from there, you will ssh the server you want to connect to.
It seems like using a username and password to use the SSH because the username and password can be typed in from any computer whereas a private key needs to be stored on every computer you use for SSH.
If you can remember the passwords for all your servers, then your passwords are bad. If you need to access a document where the passwords are stored in order to remember them, then you can also retrieve your private key.
Using password authentication on your systems is bad practice for multiple reasons:
As Atsby said, being able to connect from any computer also enables any computer to potentially connect to your systems, even compromised ones. Sticking to trusted machines is in your best interests.
With password authentication enabled, a remote attacker can always bypass public key authentication and log in with your password. You are now 100% vulnerable if one of your machines is compromised with a keylogger.
Furthermore, if you encourage the behavior of logging in from random remote machines, you will eventually stop checking the remote server's fingerprint is ok and you will be exposed to all sorts of MITM attacks! This means you believe you are connecting to the server you wish to join, but in reality you are connecting to a different server, or your connection is decrypted by an intermediary then re-encrypted and sent to the real server.
a private key needs to be stored on every computer you use for SSH.
The second paragraph (specifically, I'm focusing on this part, that I quoted above) is correct: if you log in from multiple machines, you'll need to have the private key accessible from multiple machines. This means a few things. First, each machine that you log in from will need to be trusted to not do terrible things with your private key. Malicious machines cannot be trusted. Second, you'll need to figure out a way to get your private key onto those machines. That may be inconvenient.
There are a couple of ways around this, if you want to be able to log in from multiple machines. One way is to log in from a less secure machine to a secure machine, and have the secure machine store the key(s) that work with various other systems. This still leaves a weak link in the security chain, because then an attacker could try to get your password to the middle machine. Once that is obtained, the attacker could probably access the keys that get you into other systems. However, the good news is that you're not needing to place your private key on every computer you go to, so this does offer a convenience factor.
Another way is to use one-time credentials. (More commonly known as: one-time passwords.) With this method, you can use a trusted device to generate a passphrase. I know some people have used their smart phones. Then, you really don't care if your key is compromised (stolen/copied) after you have successfully used the passphrase, because the passphrase isn't any good after that anyway.
Working with one-time passphrases may be slightly more convenient if you typically log into the same system, as some software might remember some details (like a sequence number) which would require less manual work on your part. You could combine these methods: use a one-time passphrase at the start of your SSH activity, and log into a trusted system. Then reference the key files on that system to log into other systems.
Therefore if you want the ability to SSH into a server from any computer you should stick with username and password.
Therefore, the third paragraph is a part of your premise that I'm not agreeing with, because I interpret your question as meaning that you should stick with the way you've been doing things, using a standard password. Instead, use the passphrases that are part of the "one-time password" methods. This way, you use a more complex security method (providing better security, like what key files do), but use one that doesn't require untrusted machines to use key files.
To point you in a right direction, OpenSSH supports one-time passwords via the skey method, using a program called skeyinit. Then, to generate the passphrases on a mobile device, OTPdroid for Android also supports this. There may be other workable solutions, but this is simply describing some resources that are known to work well with each other.
On a side note: with the situation you're describing (multiple systems), I highly recommend that you get familiar with terminal multiplexers (tmux or screen). It will let you do some work (for instance, logging in from the middle system into other systems), and then detach a session. Then, after you perform the initial login from another machine, you can resume a detached session, and some of your mundane work (like logging into other machines) might not need to be done again.
