Random Contacts saved in my iPhone 6
Check if either


You're logged in with someone else's icloud or email accounts in settings


or


Someone you know (kid, spouse, etc.) is using YOUR icloud account on their device.


Easiest way to tell: change your icloud password and see if anyone screams, and if the problem stops.

Another source of them might be if you share a computer and multiple people sync their phones to it, it might be syncing your phone book with the computers'