Will it void the warranty if I use a USB to Lightning charger with my iPhone 13?

Nope. Works fine. Fully supported.

“You can use any of the adapters listed below to charge your iPhone, iPad, Apple Watch, or iPod”

About Apple USB power adapters - Apple Support

Same cable from the old iPhone will work, too.

It will charge more slowly than would a newer and higher-wattage adapter.

That is not true whatsoever.

The reason Apple no longer includes the charger in the box is to encourage users to use what they already have.

—Optional Purchase—

Your iPhone is compatible with MagSafe wireless charging (which is faster and more convenient).

For that to work, you would need:

1. 20W USB-C Power Adapter.
2. MagSafe Charger.

PS: It occurs to me that the Verizon rep might be confusing the cabling. New iPhone models arrive with a USB-C to Lightning cable, and not the older USB-A to Lightning.

If used with an iPhone, your older USB-A charger will have a USB-A to Lightning cable for your older iPhone.

That cable was used with older iPhone models, and still works with newer Lightning devices.

If you don’t still have the USB-A to Lightning cable (or this charger wasn’t used with an iPhone), you’ll need to acquire a USB-A to Lightning cable from Apple or a (preferably MFi-rated) cable from a third-party to use the older USB-A charger.

Apple well along switching over to USB-C connectors for most connectors on most devices. Smaller, reversible, ten to soon twenty times the available power than USB-A, and multi-protocol support, too.

But the 5W, 10W, and 12W USB-A chargers? They’re compatible.

A lot of phone store sales say the stupidest things, and that's one of them. As long as you use a reasonably good quality power source (doesn't necessarily need to be on any official Apple list) and an Apple OEM or "Made for iPhone/iPad/iPod" (aka MFi) USB-A to Lightning cable, you should be fine. Apple specifically says that any official Lightning cable is fine with any model of iPhone with a Lightning port.