As you have discovered the M3/M5 commands are far too slow acting for laser use.
The commands M11Px and M10Px (where x=the Output# being switched) are motion linked and were added to Mach3 for laser (and plasma) use.
If your laser trigger Output Pin number is mapped to Output#1 then the command M11P1 will turn on the Output Pin and the command M10P1 will turn off the Output Pin - provided the commands are followeed by an axis movement.
So...
To get started, Configure your M3 / M5 Pin number to Output#1 and replace the M3 commands in your Gcode with M11P1 and also replace the M5 commands with M10P1 and that is basically it.
There are various laser Post Processors to create this code available for different CAD/CAM softwares.
There is an example Gcode (Trispokedovetiles(laser).tap) in the .zip file here;
https://www.machsupport.com/forum/index.php?topic=18345.0Tweakie.