Received message saying someone was using my Apple ID on a new phone on Facetime

There are two things you should do -- and do quickly. First, use your phone to open "Find My". At the bottom of the screen, tap on "Devices". You will soon see a list of all of the devices using your Apple ID. You can click on any device name to locate that device on a map.

Once you have located the unknown device, you can mark the device as lost. Once you have done that, immediately change the password on your Apple ID. The person holding that unknown phone will then have no choice but to contact you in order to get the phone unlocked, since (s)he will no longer know your password.

Good luck.