How to prevent tracking or hacking of a used phone
You can check if your phone is currently unlocked/rooted in bootloader (volume down+power for a few seconds when phone is off should do it. Otherwise Google for your phone.) I guess there's no way to check if your device was ever rooted.

Indeed, the safest* is to root the phone yourself and flash a ROM. Another advantage of this is that you are up-to-date.

*Of course, there's always the potential risk that rooting fails and your device explodes :)