Hello Verr_cz,
It sounds like your lost phone is still trackable in Find My iPhone at http://www.icloud.com, and your contacts are being deleted and replaced with someone elses. You have a couple of options here. You can change your iCloud account password to stop any further unauthorized access to your account with the following article:
iCloud: Change your iCloud password
http://support.apple.com/kb/ph2617
You can also remotely erase your phone using Find My iPhone at http://www.icloud.com with the following article:
iCloud: Erase your device
http://support.apple.com/kb/ph2701
You can also choose to do both of the above if you have other content you do not want them to have access to. There is also a nifty feature called Activation Lock that is enabled automatically when you set up your phone with Find My iPhone. Take a look at this information about it:
iCloud: Activation Lock
http://support.apple.com/kb/PH13695
With iOS 7 or later, Find My iPhone includes a new feature called Activation Lock, which is turned on automatically when you set up Find My iPhone. Activation Lock makes it harder for anyone to use or sell your iPhone, iPad, or iPod touch if it’s ever lost or stolen.
With Activation Lock, your Apple ID and password are required before anyone can:
- Turn off Find My iPhone on your device
- Sign out of iCloud on your device
- Erase and reactivate your device
Thank you for using Apple Support Communities.
Take care,
Sterling