You need to login using the putty on the windows machine and exit the .ssh/authorized_keys file and add the key that you generated on the mac to the file.
Do not run the command
scp -2 -P 50022 -v ~/.ssh/id_rsa.pub newuser@111.222.333.444:
That will over write the existing key on the server, and it will not work either as the server only accepts key logins.
I freely concede that I have no knowledge of the inner workings of keychain, but it's completely reasonable that a local ssh agent should be upset not to have a public key that corresponds to a private key that it does have.
Consider what happens when you approach a remote server to authenticate. The remote server knows, from its authorized_keys file, that it's prepared to accept a client that can prove it has the corresponding private key to each entry therein. But how does it ask for that from the client? It can't give each private key itself, nor any property thereof, because it doesn't have it; all it can do is present the public key(s), or fingerprints thereof, that it will accept.
If the client has any of those those public keys, it can immediately select the matching private key, and make a response which the server will accept as correct. If it doesn't have those public keys, what is it to do? Try every private key in its repertoire in turn? A better recipe for unsafe information disclosure could scarcely be imagined; a black-hat would only have to set up a man-in-the-middle attack on a single new connection to harvest legitimate responses from every key in your keyring.
It's possible that keypairs have some kind of internal numbering, but this would be completely arbitrary and unwise to rely on. There's no guaranteed internal property tying a private and public key together, because there's nothing shared by the keys in a keypair, save that one is (hopefully) the only entity that can undo what the other does.
No, the best way for the client to select the right private key to use to any given server is to have the matching public keys to assist it in key selection.
Best Answer
Your private key has more information than your public key does. Whereas the public key only conveys the encryption exponent (e) and the modulus (n), the private key additionally includes a decryption exponent (d) and the two prime factors (p and q) of the modulus. The private key essentially has a public key inside it.
[Encryption: ciphertext = message^e (mod n); Decryption: message = ciphertext^d (mod n)]
To see all of the data in your private key file:
Edit: The private key file apparently doesn't have the encryption exponent, but it has exponents d_1 and d_2, where d_1 = d (mod p-1) and d_2 = d (mod q-1). These are used to speed up decryption -- you can split your decryption exponentiation into smaller parallel exponentiation calls, which ends up being faster than one big m=c^d (mod n) for big d and big n.