How do I track a stolen iPhone when the passcode has been changed?

That your old iPhone was stolen would not, or at least should not, affect any new phone. How exactly are you trying to get into your new phone and what is happening when you try?

As to finding your stolen iPhone, if you set up Find My on it before it was stolen, see:

If your iPhone or iPad was stolen - Apple Support

If you did not, then there's nothing you can do other than report it to the police.

Regards.

If Find My was turned off when the thief stole the phone, you cannot track the phone. In addition, this makes it easy for the thief or fence to reset the phone and "make your phone their own."

If "someone who knows" your passcode and/or Apple ID password gave the thief either of these things, then the thief also has the means to ransack your data. If you have not already done so, I would strongly suggest that you secure your Apple Account, especially if it has any backups or synchronized data that you hope to restore to your new phone.

If you think your Apple Account has been compromised - Apple Support

Hello~ Did you give the thief your passcode? Did they also change your Apple Account password?

~Katana-San~

Is there anyway I can find the location of my phone. The location service was turned off when they stole it

Sorry, but there is no way to locate the phone.

The someone you know who gave them the passcode.....in effect gave them your phone and everything on your phone. That someone owes you a new phone.

Hopefully, you will not give anyone the passcode for your new phone.

Help you do what? If you still are referring to trying to get into your new phone, you need to give us more details. Otherwise we have no idea what you're trying to do and what is going wrong.

I would highly recommend looking at the resources the previous users have provided. Although you won't be able to track its location, you can report the crime in your area, if available