Iphone is hacked; a phone call told me so

The first time that they called you, they probably got your number

• By dialing all of the numbers on some marketing list that they purchased from other spammers, or
• By using a robo-dialer to dial all of the numbers in your area code

Once you called them back, they got your Caller ID information from that. Now they not only have your number, they have it marked down on their end as the number of someone who answered.

None of that required hacking your phone. But they still do have access to your phone in the sense that they can make further spam calls to it, or send spam text messages to it.

Blocking spammers on your own device can be like playing "Whack-a-Mole", but in case you want to try:

Block or avoid unwanted calls on iPhone - Apple Support

Block, filter, and report messages on iPhone - Apple Support

P.S. – By the way, don't be too quick to trust any Caller ID that you see on your phone. Spammers and scammers can, and do, send fake ones. Sometimes they even use your own number as their "Caller ID"!

Someone is trying to scam you. It's often a good idea to only answer calls from people you recognize and if someone really needs to reach you, they'll leave a message. Ignore whatever they told you and move on with your day. Scammers are quite creative and do everything they can to scare you into either buying services or tools you don't need for issues you don't have. No one can hack your phone from a phone call.

Read this --> Recognize and avoid social engineering schemes including phishing messages, phony support calls, and other scams - Apple Support

> I think someone still has access to my phone and I just want to know if I should just move to a new device to get away from this

As others have noted, you were the victim of a scammer. They call literally thousands of numbers at a time with a somewhat legitimate-sounding message hoping to get someone to call them back. it only takes a handful of people to fall for their trap to make it worth their while.

That said, 'move to a new device' won't make an iota of difference. They have no hold or control over your device. All they have is your phone number. Changing phones won't make a difference. You'd have to change your phone number to make any difference, and that comes with other costs such as updating everyone you know with your new number.

Best to block their number ( Block or avoid unwanted calls on iPhone - Apple Support ) and never interact with them again.

They have no access to your phone. The mistake you made was calling them, so now they think you can be easily manipulated in believing what they say. You received spam, because your phone number shows when you call them. In the future, never respond to any such message a deleting them is all that is needed. The call that stated "No Caller ID" should have been a clue.

You were scammed. No one has access to your iPhone unless you gave them your Apple ID and password.

Don’t believe these kind of calls. They’re trying to get you to do something to their advantage.