I used to setup as new, but I have a lot of apps, and most of those apps require logging in with passwords which is a painful process to have to go through.
I haven't seen any data to confirm that setting up as new results in a 'faster' phone, although restoring from an encrypted iTunes backup probably brings over some unwanted remnants from a storage perspective (since iTunes backups are basically an iOS backup + user specific data/settings).
What I've settled on is restoring from a 'clean' iCloud backup. iCloud backups are basically metadata backups (what your settings are, what apps are installed, etc) along with some binary data like lock screen and home screen images (if you're not using built-in wallpapers), app data, health data, etc.
Best way to get a clean iCloud backup is:
Perform an encrypted iTunes backup in case something goes wrong
Delete/turn off iCloud backup (this will remove any app data for apps that are no longer installed)
Power cycle your phone (this will clear any in-memory or on-disk app caches)
Turn on iCloud backup
Perform an iCloud backup
Setup new iPhone from iCloud backup
Hope this helps.