If you have pasted the public key to the authorized_keys file in the format shown in the question (---- BEGIN SSH2 PUBLIC KEY ----), it won't work.
You have to use the one-line format shown in PuTTYgen labeled "Public key for pasting into OpenSSH authorized_keys file".
It would be like:
rsa-key AAAAB3NzaC1yc2EAAAABJQAAAQEAs2f7SVX8KOu0RvzQh0r6uwWS/TB5uXO7+QEsCxF+0CF3vwLeOn+cNw1HQHy7EDHhGw4eYvL/ErbIyv4I8HgGe/IFe4qPUOMy3vtzZNjqemBsy32Lgsx/flQBYLW+XzYC4LeZv3TSZjfYyIk8ilRBOzdkP4CdYeK0rPRbPPtlLQY5l95h1UnmuORNgA93yLqvKI/dSnkvKyTrJoCGbRXr5pept5Y9LSEHYlEadrBpogsF9LYj/HDeaoIjBhGQu+CZRDzZSxgtv3+nePEkoeV1xC8tyJ83JiHcrX3PbjouJHLLTWa2tl40XM913dkUSsbha2Fbd0wBchry9y2BlpUA9Q== rsa-key-20150209
Generally you should be very cautious when you get
WARNING - POTENTIAL SECURITY BREACH!
The server's host key does not match the one PuTTY has cached in the registry.
It's an indication of MITM attack.
See also PuTTY documentation for WARNING - POTENTIAL SECURITY BREACH! (what is the main part of the message, which you somehow omitted in your question).
You never get this message for a new server. Unless, of course, the new server reuses IP address/hostname of some discarded server. In which case, it's ok to ignore the warning.
It is, of course, a public key that is cached by PuTTY. A private key is secret and it must not be accessible to anyone, except for the server administrator. So there's no way SSH client can get it.
The server can indeed have a number of key pairs for different algorithms (one for each algorithm, like RSA, DSA, ECDSA, ED25519). The client and the server will agree on the best algorithm to use (the best out of those supported by both the server and the client).
The key pairs are usually stored in /etc/ssh (on Linux with OpenSSH).
Though wording of your question hints that you may confuse the server/host key pair with the key pair you use to authenticate to the server.
See my article on Understanding SSH key pairs.
Best Answer
To be clear, the server isn't actually re-sending your public key back to you. The server has its own completely separate key that it's sending to you – the "host key". Both the public and private parts of the host key are stored in /etc/ssh.
The server doesn't just send the public key; it also sends a signature made using the corresponding private key, which the client can use as proof. (The data being signed is unique for each connection.) An attacker could send the same public key but couldn't produce a signature.
This is also how certificates work in SSL/TLS (HTTPS and such).
Your own authentication key is also verified by the server in the same way – i.e. PuTTY doesn't only send your public key alone, but uses your private key to sign the message, so that someone else couldn't log in as you just by looking at your authorized_keys file.