AC is only one form of defense, and doesn't typically grow with level.
What you're running into is the concept of Bounded Accuracy. One of the design pillars of D&D 5e is the idea that even high level characters don't have passive defenses that make them invulnerable to the attacks of lower-level characters. It is an intentional feature of the system that level 1 characters with an attack bonus around +5 can hit the AC of a level 20 character.
What this means is that, as characters level up, one of the ways that they get more powerful is that they hit more often, and are hit more often in turn. It's totally normal for most attacks to hit in a high-level combat where everyone is swinging with attacks above +10.
Generally speaking, without magic items, the highest AC a character can reach is in the low 20s. A paladin with a shield wearing plate armour isn't going to go much past 20 without magical assistance. A breakdown of how a character hits maximum AC can be found here. In short: Barbarians can get their AC a little higher than 20 without magic because of their higher stat cap, and magic item can push your AC another few points.
What you're missing is the other kinds of defense that make a high level character hard to kill. Higher level characters have many more hit points and access to defensive buffs than low level characters, and generally have more passive and active defenses in general. For example: your Paladin player will eventually get an aura that protects the party from various effects, based on their Oath. Also, Lay on Hands acts as an effective HP buffer that makes the party much more difficult to take down as the Paladin keeps them healed. In addition, your casters likely have a large number of battlefield control spells that make it possible to shut down enemies before they can even attack at all.
Your players probably won't have their AC increase, but they will get many more ways of dealing with threats defensively.
Note: The link to the Wizards article on Bounded Accuracy goes to the Wayback Machine, because the original article is no longer on the WotC site.