If you recently got the new iPhone, and you use two-step verification for your Apple ID, remember to update your list of trusted devices. You can do so here on Apple's website.
As part of Apple's two-step verification system, you register one or more trusted devices. But setting up a new iPhone and/or erasing an old iPhone won't automatically update that list.
If you aren't currently using two-step verification for your Apple ID, I highly recommend doing so. Here's where to start: Frequently asked questions about two-step verification for Apple ID