Since you mention using a shared one, I would guess your CPU is being throttled:
Fly do offer a range of “performance” machines instead. I would guess you would get more from them and so your video would be processed faster. Could be worth a try. Then balance the cost vs. time.
Out of interest you could open a ssh console into your machine, then add/run a command like htop (if that’s not available, you could install it) to see your CPU usage while your video is being processed.