I believe the voicemails are stored on the provider's servers. Can test that by dialing into VM from a different phone and see if you can play them back. If so, should be able to retrieve them again on the new phone.
Can create voice memos from the vms:
https://support.apple.com/en-us/HT205012
Tools like iMazing save voicemail. In the case of iMazing, their trial version only downloads 1 vm, so would need the full pay version to get all of the vm.
Can't recall if the transfer process from old to new phone at initial setup moves them.
Or if backup to computer contains the vms: that can be tested by backing up the old device, setup new from that backup. If Ok, can wipe the old phone, otherwise, try the save to memos.
Basically, a bunch of things to try BEFORE you wipe the old phone.
EDIT: looks like backup via Mac gets the voicemails, as I can see that in iMazing from latest Finder backup. Assuming iTunes on PC will do same.