> Is it better to use a different passphrase on each key, or does using the same one not matter much?
Using a passphrase is highly recommended except for server-to-server accounts, which should be locked down (and specify the specific command that server can execute in the authorized_keys file - Userify[1] supports this).
You should definitely use a different passphrase for keys stored on separate computers, and it's not a bad idea to use a different passphrase for separate keys stored on the same computer, especially if they have different servers they can access. However, practically speaking, if your computer was compromised (ie keylogger etc) then it's game over anyway.
> Does increasing the amount of bits in a key really have an effect on the security of the key, or does it not make much difference in a real-world use?
Yes, it does make a difference, depending on what you mean by "real-world". Anyone less than a state-level actor will probably be unable to cost-effectively attack even a 1024 bit key, but that won't be true for long. We suggest 2048 bit keys if you are using RSA, with 4096 if you prefer extra security and don't mind slight latency during a connection, or ED25519 for keys on systems that support it. Generally the defaults are pretty good. We have a HOWTO for different OS's here: https://userify.com/docs/generating-ssh-keys-on-ec2/
> How much less secure is it to not use a passphrase on a key?
From the server's perspective, it's EXACTLY the same, but from the client (your laptop's) side, it's completely different. While it's possible that your laptop could still contain your decrypted key in its key manager's RAM or suspended state (ie unencrypted swap file etc), the use of a passphrase even on (actually, ESPECIALLY on) a non-full-disk encrypted system will raise the level of effort to access your key to near-impossibility levels, especially from non-state actors, whereas a key that has NO passphrase is a piece of cake. Use a passphrase EVEN WITH full disk encryption (for example, the evil maid attack)
> Should you use a different key per user account, per server, or per use-case (i.e. personal or work)?
If you're using a different key and storing them on different computers, you should probably use a different passphrase on each key. The passphrase (or even if one exists) is not visible to remote servers (or Userify[1] - we provide a free-text field that becomes your authorized_keys on remote servers.)
You don't need to use a different key per user account, although you can. You also should not use a different key per server.. that will turn into a management nightmare. It's perfectly ok to use one key everywhere, but you should probably use a different key on your laptop and desktop, or if the keys have different levels of access (Userify[1] can automate that for you too).
> How/Where should private keys be stored on a device using them?
Ideally on a device using full-disk encryption, including swap and laptop suspend space, to prevent access to a decrypted key in RAM (you are using a passphrase, right?). However, FDE does not protect you from other compromises on your system (i.e., another user that gains escalation to root and installs a key logger), and does not protect against a compromise of your BIOS (i.e., Intel UEFI) or boot process (evil maid attack again).
> What are some of the pros and cons from a security standpoint, and how may doing different things affect the usability of a key?
Keys are safer than certificates because there are less moving parts and no outside requirements for your internal CA or dependency on a CA that might go down. Keys can be a management nightmare at scale, but there is software to manage them (ie Userify[1], ManageEngine[2], BeyondTrust[3], ssh universal key manager[4], keybox[5] (free/open source), etc). If you are doing a small project with few team members, you can also do management with Chef, Puppet, etc, or just by hand.
In terms of usability, a real key solution that manages keys across entire groups of servers with a few clicks can be really helpful... you can do all of the regular SSH things like tunneling (replace stun/sslwrap, etc), proxying all of your other traffic (SOCKS5), keep SSH connection alive (autossh etc), smart ban based on failed attempts (fail2ban, deny hosts), forward encrypted X11 or VNC connections, forward SSH itself (tunnel SSH within itself), and so much more.
We're going to start blogging about all the awesome things you can do with SSH soon, since it's really an amazing and deep protocol.
1. Userify https://userify.com Free cloud and on-premises versions available; full disclosure: I work there
2. ManageEngine: https://www.manageengine.com/
3. BeyondTrust: https://www.beyondtrust.com/
4. SSH Universal Key Manager: http://www.ssh.com/ (no TLS?)
5. Keybox http://sshkeybox.com/