Search for old/deleted instance

I had setup a Ubuntu instance with Linodes, but for some reason it has been removed or deleted without my knowledge.
There is nothing on my Linode dashboard.

When I try to SSH in, I get the following error:
"ECDSA host key for xxx.xxx.xxx.xxx has changed and you have requested strict checking."

Any ideas?

Thanks