Is it normal for my voltage regulator to run this hot on my camera battery rig?

The heat isn't a flaw in your setup, it's how linear regulators work. Your pack is putting out somewhere around 7 or 8 volts, the camera only wants about 3, and the chip burns off that difference as heat. So you're basially running a little electric heater in series with your camera. No heatsink will ever fully fix that, beacuse the heat is the whole job the chip is doing. That's also your answer on battery life: every bit of that lost voltage is charge from your 18650s going straight into the air instead of into the camera. You could easily be getting double the runtime out of the same cells with a better setup.

The fan would work, no question. Zip tie it over the heatsink and the chip will stay touchable. But it's a band-aid, and now you're spending some of your hard-won battery juice spinning a fan to cool a problem you created in the first place.

The proper fix is cheap and boring: pull the linear chip and put a small buck converter module in its place. These switch the voltage down instead of burning the difference off, so they stay barely warm even under load, and they draw a lot less from the pack. I did exactly this swap on a portable radio build a couple years back. Same story, linear chip cooking through a heatsink, swapped in a little module the size of a thumbnail, and it went from finger-burning hot to lukewarm, plus the runtime roughly doubled. Set the output voltage with the trim pot on the module and check it with a meter before you hook the camera up, and double check your polarity. Some cheap modules misbehave if the output sees voltage before the input does, so wire it up camera-off. Ten minute job and you'll wonder why you fought the heat at all.

One thing to add since you're running 18650s raw: no protection circuit on that pack means you can run the cells down too far and ruin them. I kept a little voltage meter with a clicky switch inline on mine after cooking a pair of cells the same way. Camera draws power the whole time it's awake, so you'll flatten them faster than you think if you leave it hooked up between shoots. Also worth adding a simple power switch so it's not sipping from the pack overnight.

This makes sense of something I did last year. I made a little power pack for a portable game console and it ran warm the same way, but I never figured out why and just assumed that was normal. Turns out I was doing the same burn-off thing with the old-style chip. One thing I'm fuzzy on though. When you set the output with that little screw on the new module, does it drift over time? I turned one of those once and the numbers kept moving for a bit after I let go of the screwdriver, so I never trusted it after that.

Agree with the swap advice, did basically the same thing on a trail camera rig I built for the shed. Used one of those little modules off a board I had spare and it barely gets warm now even after a full afternoon out there. One tip from that build: set the voltage before you attach anything and mark the position of the screw with a paint pen, because bumping it with a finger while mounting it in a tight spot is easy to do and I had to redo mine once.

One thing that tripped me up on a similar build was just getting power into the camera cleanly. Mine had a battery door that wouldn't shut with wires hanging out, so I pulled apart a dead AA, gutted it, and wrapped the wires around the shell so the camera thinks real batteries are in there. The bit of thin wire from an old USB cable was what made it work, fat wire wouldn't sit flat under the door. Soldered to the little nubs at each end and taped the seam. Closes flush now and the connection doesn't work loose when I'm fumbling with the thing mid-shoot.