They don't report execution time in the paper. It's likely that the A* implementation would run faster in terms of CPU or wall clock.
Transformer model that optimally solves previously unseen Sokoban puzzles 93.7% of the time, while using up to 26.8% fewer search steps than standard A∗ search.
Doesn't fewer search steps imply faster?
No, each step could take significantly more time (and resources).