@dbemowsk Great looking project!
Whilst you have gone to some length to post your project you left out a crucial bit of information - that is, how much current do you need at 5V?
Your original problem with 5V relays was probably due to not enough current available at 5V, nothing to do with the relays themselves. You might also want to investigate latching relays as that would save a lot of energy and they come in 3.3v versions as well......
Once you know the current required, search for an LDO dc switching regulator that gives about 50% more than this (just for safety and longevity of components) and then you have the answer.
As you are already soldering your own boards then adding a regulator and some caps shouldn't be too much of an issue for you.