Why does a SSH public key sit on the server and not with the client?

Solution 1:

Keep in mind that the server DOES have a private and public key which is completely separate from the keypair you generate as a user. The private key for the server is usually stored with the server configuration and the public key is transmitted by the server when you attempted to connect. You client compares the server's public key against your known_hosts file. If used properly, this prevents MITM attacks.

You have the private key for your personal account. The server needs your public key so that it can verify that your private key for the account you are trying to use is authorized.

So using your example. Both Bob and Alice have private keys and public keys. The public keys which have been shared before hand or as part of the connection are used to verify the data encrypted by the private keys is legitimate. If the client doesn't have the public key, or has a different public key you will get a scary warning. If the server doesn't have the clients public key, you will not be allowed in.

Solution 2:

You as the user are the one to provide the information that you are you when you log in. So for the sake of authorization, you need the private key because the server will ask anyone who pretends to be you (attempts to logs in with your name) to prove it.

The way it works is that the server sends you a bit of text, asks you to encrypt it and decrypt it with your public key. Only the person with your private key can do this.

Solution 3:

It holds the public key for convenience. Otherwise you have to create a PKI - something similar to SSL CA.

The idea would be to check the public key fingerprint when the ssh client ask you to accept the remote server key.