There are 2 major things happening in SSH connections:
Server Authentification & encryption
The server sends you his public key and you have to trust it. You could manually get it before that and in an ideal security environment you would never connect to an SSH server BEFORE you know his public key is correct. That what CAs are for, they sign a servers public key. In most SSH environments you just accept the pubkey of the server as client. This is the initial "do you want to trust this server and add it to your list?"-question. The server pubkey is stored under .ssh/known_hosts at the client in Linux systems.
The actual encryption of the connection isn't asymetical.
This is a huge misconception many people have about private/public-key encryption.
It would be WAY too slow. What really happens is that server and client generate a shared secret (aka a long password) which is symmetrical encryption for this one session. The client and server use asymmetrical encryption until they agree upon a shared secret. After that they switch to symmetrical encryption with this shared secret as key.
This type of encryption is the most common and called hybrid encryption, though nearly everybody (wrongly) calls it asymmetrical encryption.
An example for "real", pure asymmetrical encryption is Mail encryption with PGP, because EVERY message is encrypted asymmetrically.
Also: The shared secret isn't stored permanently, every new session a new shared secret is negociated.
Client Authentification
This is a whole different thing, this is what can be password and/or key-based authentification. The public key of the client (located under ~/.ssh/id_rsa.pub) must be present in the servers authorized_keys file (e.g. for root: /root/.ssh/authorized_keys). Before ssh-copy-id existed people would do something like
cat ~/.ssh/id_rsa.pub | ssh root@server "cat >> ~/.ssh/authorized_keys"
to append your key to the servers authorized_keys.
The client certificate is NOT used for encryption, just for authentication.
IMPORTANT Edit: Made post more clear regarding ssh-copy-id to prevent misunderstandings.
As of now, ssh-copy-id is the best practice way to add a clients public key to a server. I just posted the cat method to show which files are manipulated on both sides to show the connection between private and public keys and how they are stored.
When using cat there is a risk to forget a ">" for example which would overwrite your authorized_keys file (in Linux ">>" means append, ">" means overwrite). Be responsible when manipulating configuration files directly.
Thanks @Rallph for pointing it out.
