I'm a short female and when I started diving, I was doing the 24 minute dives on an 80 at 25'.
Lots of stuff helps. My dives on a PST HP 80 tend to be from 45-60 minutes now. My best dive time had me down with an 80 for 1:17, and that includes time fighting with the anchor and that had a max depth of 45'.
First off. I was struggling to get down because I was so excited about the dive that I was gulping air at the surface, which is apparently common. As a result, for my first 20 dives, I was using between 24-26 lbs to get to the bottom. I now use 14. That made a HUGE difference.
I used to do a lot of finning and fast finning because I wanted to "find stuff". I now see more stuff because it isn't like the seals are hanging out 75 yds away from you waiting to see if you'll find their secret gathering place. Now, I dive slowly.
Don't fight stuff at the surface. Find ways to work around it. This last weekend, I discovered the joys of clipping yourself off to the boat in heavy surface current. SO much nicer.
Be comfortable in your gear configuration. I was using an ancient SP jacket that did work quite well (for the 50 bucks I bought it for), but not wildly comfortable on me and made for a medium sized man, so it pressed in the wrong places, which increased my breathing rate. I swapped to a Transpac, which doesn't squeeze me anywhere. Air consumption went down.
Don't hang onto your inflator hose constantly. Using your breathing to hold your buoyancy uses far less air than constantly inflating, deflating. That's wasted stuff. Also, if you're overweighted (like I was), you often end up putting a lot of air into your BC that you now can't breathe.
Have a comfortable regulator. If breathing is work, you'll breathe harder.
If you have any habits that increase your breathing effort (like smoking), that can contribute.
If all else fails, get a camera setup
. That more than anything else extended my dive time because I ended up spending the majority of dives doing a dead body impression on the bottom while trying to get the right shot of sessile life forms.