I don't quite understand the theory behind keeping public keys on the server. In the lockbox analogy of public/private keys, to unlock Alice's box, Alice holds the private key while the public key is distributed to Bob. It would seem that the server plays the role of lockbox, so why does it hold the public key?
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.
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.
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.
I would say that a better analogy is that the server's public key is the open lockbox with a latch that you can close (but not open), only the server can open it. The real question is whether you trust the public key (is that really Alice's Box?) , wherever you get it from it is public by definition, and that is what PKI's are about.
A public key is a very large number, mathematically derived from your private key.
It is derived in such a way that the two numbers are linked,
but so that the private key cannot be discovered by anyone who only knows the public key. The public key is what you send to other parties, to whom you want to authenticate yourself, or to whom you want to send encrypted messages. The public key is not sensitive, and does not need to be protected. It can be disseminated publicly. email@example.com