First of all, to perform authentication, you don't need an an "encrypted" password; storing an encrypted password puts your users at risk and I strongly discourage it. Because users are ignorant, they are likely to use the same password for their bank account and your game. Help them stay safe by taking good care of that password.
Instead, store an irreversible "hash" of the password and a random "salt". There are many questions about how to do this on StackOverflow, and a couple of their answers are almost correct.
The part of your question that is unique is that you are specifically concerned with the performance of the authentication process. This is an interesting question, because a good password protection scheme is actually designed to be a little bit slow. This is to defeat an attacker who is trying to guess a password in an "offline" attack, where he can test billions of passwords. The slower the algorithm, the fewer attempts he can make.
The algorithm I recommend for protecting passwords is actually a key derivation algorithm called PBKDF2 (PBKDF1 would work also), which is described in PKCS #5. One of the tuning parameters of these algorithms is a number of iterations. You can profile the algorithm on your server, and adjust the number of iterations until you find a number that meets your performance requirements. Even my laptop can perform thousands of iterations per second, so I'd probably start with around 2000 and work from there.
If you are actually talking about encrypting all of the traffic between the client and server, use AES. It was selected because of its speed even though some other ciphers in the competition are probably more secure. Specifically, use an AES cipher suite in an SSL connection.
The expense of a secure connection is the key agreement (or key transport) that happens when the session is set up. The on-going encryption (and message integrity computation) adds very little overhead.