long SSH password vs SSH Keys

Using amazon's EC2 Service, which is awesome in every regard.

Only problem is, I have problems logging in with the SSH keys they automatically genarate. I have no idea what the problem is, but have no desire to look any further, as I need to get back to working on my application. ...

tl;dr; So, what are the security implications that make SSH keys so much stronger than 20+char long passwords? From my understanding SSH keys primarily protect against brute force attacks - but if I created a username and password with 20 or 64+ charectors...how much more secure would using keys be?

Well, a typical SSH key is somewhere around 1024 or 2048 bytes. That's a chunk longer than any password you're going to type in a reasonable amount of time. The whole advantage to ssh keys is that your key password (you do set passwords on your ssh keys, right?) is effectively a proxy to the higher security of the key.

The big advantage to keys is that your password never traverses the network. A relatively common attack is to install a trojaned version of the ssh server; when people type in passwords, the modified server records them and sends them elsewhere. This is a particular problem because these same passwords often are used for access to a number of systems/services.

ssh keys largely eliminate this problem.

Ssh keys are usually simple to set up. You stick the public key on the remote system in the appropriate authorized_keys file, and configure your local ssh to present the appropriate private key when you connect. If you're having some specific problems we can probably help you work things out.

A 20 character password is at most 640 bits of entropy (4 byte characters, 20 characters), and that's assuming a completely random unicode password involving 4-byte characters is used. For Ye Olde 8-bit ascii that's closer to 140 bits. And most passwords are not completely random.

A generated SSH keypair is a lot longer then that, generally between 1024 and 2048 bits but not limited to that, and can be password protected for extra protectional credit.