In that case, they should be lieutenants. Also, I think Edhellos should be lieutenant of Angrod, since she doesn't do any healing.I think it might be okay to use the term 'herald' here - this might be an opportunity to show that a herald could be male or female.
We were going to try to show that heralds were more typically healers not fighters, though. So, they're high-ranking in this society and play a pivotal role in the military, but...not exactly the kind of person you'd want at your back in a skirmish.
So, knowing that, would you prefer that this person be a lieutenant (ie, military rank for a skilled combatant) rather than a herald (support role that is high in the command structure, but not a skilled fighter)?