That answer depends on things we cannot see.
Usually, Messages syncs to iCloud. When you 'delete' a message, it's simply flagged as deleted, but it still exists in the Recently Deleted folder.
When you sign in with a new device, it syncs with iCloud to get the current state of various applications and data. Therefore it should still see the same 'Recently Deleted' messages, even though they weren't deleted from this device.
You can verify this by deleting a message on your phone, and you'll see it appear in the Recently Deleted list on your MacOS system (assuming you have one).
If you're not synching Messages through iCloud, then all bets are off. I would expect it to still exist if you use Quick Start to setup the new phone, but I've never tried it.