ssh using old IP for a host

[Lucio]

I've updated the IP address for a server.

The DNS record is propagated: host, nslookup and dig commands all agree 
on the new IP address and so do all services online to check the DNS 
record propagation.

However

$ ssh servername

still tries to connect to the old IP address. I've already restarted my 
notebook but nothing changed.

I'm using Debian sid.

Any clues about what is caching the old IP address?