I'm sure Aseprite could be further optimised to press down the constant factor, but it is performing a rect packing algorithm among other things, which is an NP-hard problem.
The bin packing problem is NP-hard, but rectangle packing is "merely" NP.
However, most people just use a recursive biggest-fit-first ¹), a simple heuristic that is surprisingly hard to beat for most workloads.
I couldn't figure out what Aseprite is doing from their website or documentation, but if it's not that then it might be worth it writing your own sprite packer.
> The same doesn't apply to the player sprite, as Aseprite takes minutes to compile the atlas for the nearly 1000 frames we have.
Why does compiling a sprite atlas for the player take 60ms/frame?