Linear regulators would usually be a poor fit there indeed for obvious efficiency reasons.
You'll need to dig a little bit to find a step-down converter that'd be appropriate, admittedly, but it's not out of reach.
With those specs, it's not going to be cheap though. One example would be the LTC3631. With 125 uA of quiescent current in active mode and 3 uA in shutdown mode, and a very wide input range, max 100 mA output.
The overall efficiency will be way, way, way above anything you could get with an LDO here. Except maybe when you draw no current at all, in which case you could use a shutdown mode. But I know, it's NOT cheap.