How to ssh to localhost without password?

Question

EDIT: Putting exactly what was done

I need to SSH localhost without 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

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: 

Answer 1

I did following 3 steps to create the password less login

1. ssh-keygen -t rsa
Press enter for each line 
2. cat ~/.ssh/id_rsa.pub >> ~/.ssh/authorized_keys
3. chmod og-wx ~/.ssh/authorized_keys