How to SSH to localhost without password?

EDIT: Putting exactly what was done.

I need to SSH to localhost without a password, the usual way of doing it (with public keys) do not work.

user@PC:~$ rm -rf .ssh/*
user@PC:~$ ssh-keygen -t rsa > /dev/null 
Enter file in which to save the key (/home/user/.ssh/id_rsa): 
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
user@PC:~$ ls .ssh/
id_rsa  id_rsa.pub
user@PC:~$ ssh-copy-id -i localhost 
The authenticity of host 'localhost (::1)' can't be established.
RSA key fingerprint is f7:87:b5:4e:31:a1:72:11:8e:5f:d2:61:bd:b3:40:1a.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added 'localhost' (RSA) to the list of known hosts.
user@localhost's password: 
Now try logging into the machine, with "ssh 'localhost'", and check in:

  .ssh/authorized_keys

to make sure we haven't added extra keys that you weren't expecting.

user@PC:~$ ssh-agent $SHELL
user@PC:~$ ssh-add -L
The agent has no identities.
user@PC:~$ ssh-add 
Identity added: /home/user/.ssh/id_rsa (/home/user/.ssh/id_rsa)
user@PC:~$ ssh-add -L
ssh-rsa ...MY KEY HERE

user@PC:~$ ssh-copy-id -i localhost 
user@localhost's password: 
Now try logging into the machine, with "ssh 'localhost'", and check in:

  .ssh/authorized_keys

to make sure we haven't added extra keys that you weren't expecting.

user@PC:~$ ssh localhost echo 'testing'
user@localhost's password: 

user@PC:~$ 

So as you can see in the last command it is still asking the password !!! How can I fix that ?? Ubuntu-10.04 , OpenSSH_5.3p1

EDIT2:

Adding some info about the sshd

user@PC:~$ cat /etc/ssh/sshd_config | grep Authentication
# Authentication:
RSAAuthentication yes
PubkeyAuthentication yes
RhostsRSAAuthentication no
HostbasedAuthentication no
# Uncomment if you don't trust ~/.ssh/known_hosts for RhostsRSAAuthentication
ChallengeResponseAuthentication no
# PasswordAuthentication yes
#KerberosAuthentication no
#GSSAPIAuthentication no
# be allowed through the ChallengeResponseAuthentication and
# PasswordAuthentication.  Depending on your PAM configuration,
# PAM authentication via ChallengeResponseAuthentication may bypass
# PAM authentication, then enable this but set PasswordAuthentication
# and ChallengeResponseAuthentication to 'no'.

EDIT3: Ading result from $ssh -vv localhost

$ssh -vv localhost
...
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Trying private key: /home/user/.ssh/identity
debug1: Offering public key: /home/user/.ssh/id_rsa
debug2: we sent a publickey packet, wait for reply
debug1: Authentications that can continue: publickey,password
debug1: Trying private key: /home/user/.ssh/id_dsa
debug2: we did not send a packet, disable method
debug1: Next authentication method: password
user@localhost's password: 

EDIT4:

Just checking if the files are the same and the md5sum agree

First of all, you should understand what your doing:

user@PC:~$ cat .ssh/id_rsa.pub | ssh localhost 'cat >> .ssh/authorized_keys'

You are copying the public key .ssh/id_rsa.pub through ssh, to the same host (that is what localhost is, the same host). If you replace localhost with some other host, that would make more sense (but if you are trying this for the sake of learning how to do it, that's ok).

Once you have a copy of your public key on the remote host (or the same one you're in), you have to make sure that you use it for authentication, in your actual host, calling ssh-agent / ssh-add:

$ eval `ssh-agent`
$ ssh-add

Then, if you provided a passphrase, you'll be requested to enter it after ssh-add. If you generated a private key without passphrase, then that's it.

Have discovered the problem.

Running the server with debuging:

$sshd -Dd

I found it was not able to read the auth_key

$chmod 750 $HOME

Fixed it.

Do the following steps

ssh-keygen -t rsa -C "[email protected]"
# Creates a new ssh key, using the provided email as a label
# Generating public/private rsa key pair.

Use the default file and empty passphrase (Simply press enter in the next 2 steps)

# start the ssh-agent in the background
eval "$(ssh-agent -s)"
# Agent pid 59566
ssh-add 

Copy the contents of ~/.ssh/id_rsa.pub to ~/.ssh/authorized_keys

Ensure following are the permissions

 ls -l .ssh/
 total 20
-rw-r--r--. 1 swati swati  399 May  5 14:53 authorized_keys
-rw-r--r--. 1 swati swati  761 Jan 12 15:59 config
-rw-------. 1 swati swati 1671 Jan 12 15:44 id_rsa
-rw-r--r--. 1 swati swati  399 Jan 12 15:44 id_rsa.pub
-rw-r--r--. 1 swati swati  410 Jan 12 15:46 known_hosts 

Also, ensure the permissions for .ssh directory are. This is also important

drwx------.   2 swati swati    4096 May  5 14:56 .ssh