Yes, ultimately deontology is based on utility, unless you are saying the rules come from God*. But there is a big difference between having fixed ethical rules that are based on utility and improvised utilitarian (consequentialist) decision making. The latter is always prone to relativism; in the situation where you want something bad/immoral it is easy to come up with a rationale why it is a good idea. That’s because our judgment of how much utility an action provides is highly subjective and warped by what we want at the moment. That is based on biology: Water is very valuable when you’re thirsty, shelter is very valuable when you’re cold. Therefore, something we want at the moment will always be justifiable on utilitarian grounds. So consequentialism often means doing whatever you feel like. In a way that’s the problem with the left, they are always trading immediate destruction off against some fictional future good. I see deontology is like a constitution of utilitarian rules; you make up those rules for utilitarian reasons, but by having fixed rules you actually follow them. Consequentialist ethics amount to having no ethics. That’s how I see it.
*In that case the only utilitarian rule a person has to accept is that it is good to follow Gods rules, and bad not to do so. Which is why monotheism is based on the notion of free will and generally has a libertarian influence.