Where are my private/public SSH keys on UNIX?

~/.ssh/id_rsa and ~/id_rsa.pub usually. But it doesn't follow that ssh must create a pair and save them: ssh basically uses the SSL protocol, which establishes a session key using the Diffie/Hellman key-exchange algorithm or some variant. That means the handshake setting up the connection generates a session key and discards it when the session is completed.

Read up on the algorithm, it's pretty nifty: using fairly simple math, it establishes a key known to both ends of the connection without ever sending the key over the connection.

Your personal public and private ssh keys are normally stored in:

$HOME/.ssh/id_dsa     (private key)
$HOME/.ssh/id_dsa.pub (public key)

Or they could be id_rsa and id_rsa.pub if you created RSA keys rather than DSA keys (OpenSSH supports both forms).

But the fact that you've established ssh connections before doesn't imply that you have ssh keys. If the ssh command can't find your personal key, it will prompt you for a password for the remote system. This is less secure than using keys.

You should normally create your ssh private key with a passphrase. If you create it without a passphrase, someone who gets a copy of your private key can impersonate you. ssh-agent lets you use a key with a passphrase without having to re-enter your passphrase every time you use it.

If you didn't create a keypair, you probably do not have one.

SSH2 traffic is encrypted with a symmetric session key established using DH, ECDH algorithms or GSSAPI key exchange. Neither the host key nor the user key are used for encrypting data – their only purpose is authentication.

Now remember that SSH supports several authentication methods: in addition to publickey, almost all servers accept the simple password and/or keyboard-interactive, in which no key generation or usage takes place – the password is simply sent to the remote server for verification.

In other words, "since I've already established ssh connections before, they must be somewhere" is incorrect – the user keypair is not necessary for establishing connections.

If you did create a keypair, it will likely be in ~/.ssh/id_* – for example, id_rsa for the default RSA keypair, id_ecdsa for ECDSA, id_dsa for DSA. Although these files contain both private and public parts of the keypair, the public part is usually automatically extracted into a separate id_*.pub file for convenience (id_rsa.pub for id_rsa and so on).