Use the spell animate dead to create a custom ride
The spell animate dead creates a skeleton or—even better if it can be managed—a variant fast zombie, which no longer possesses the special ability staggered. When one can do this, then it's a matter of picking what creature to animate. As the only limits are Hit Dice and that the intact corpse be that of a corporeal creature, many good options are open, but something that could've flown naturally can still fly as a zombie, and if something had another movement mode—like burrowing—, the zombie version keeps that mode. With that in mind, I like the following:
- The fast zombie giant mantis is a Large creature with a land speed, fly speed, and climb speed. Being able to ride a and land on walls and ceilings is an interesting tactical advantage that probably requires special saddles.
- The fast zombie chariot beetle is a Huge creature with an unusual combination of land speed, fly speed, and burrow speed. As a Huge creature, perhaps the party could ride just the one.
Zombie creatures don't eat (not even brains), drink, sleep, or complain about having to go underground. While the rules for fighting atop an undead mount remain hazy, hopping off's usually better for everyone's sanity anyway. At a distance, the party will look like they're riding one or more giant bugs (apparently not that uncommon in the darklands), and up close they'll actually be riding one or more undead giant bugs, demonstrating to any intelligent foes that the party is badass enough to do that. The bugs'll die in battle or in mishaps, though, so if possible for later animating it's a good idea to gentle repose some spare intact corpses in a portable hole or, if allowed, secure them using the spell shrink item.
(While it'd be great to have a creature that could burrow through solid stone to make the trip even easier, I couldn't find any creatures of the appropriate size that could.)