I have always thought that as well. Though honestly, I always thought it should be that a logarithmic function rather than straight levels. Unlike capitals which get them divided evenly, frigates would get an equal share of a duplicate of the exp that capitals collectively get. In this way, as they get more experience, they deal more damage without having strict levels, which I hate for non-ability based things. Of course lol... Two things that computers hate are sqrt() and ln(). Both eat processors for breakfast. Seeing as how we are in a 3D game, we're already being forced to use the 3D version of the pythagorean theorem which means lots and lots and lots of sqrt() to calculate the firing ranges of ships (especially in the late game). I don't know what this would do to it.
Levels on the other hand already have the calculations run ahead of time and make things more convenient.
Perhaps instead of levels, you get a status or tired. Let's base it off of how much damage/healing a frigate/cruiser does and how much damage it takes. As you increase these numbers you'll advance through "rankings" that would simulate levels to an extent without going all out and "levelizing" frigates which I really don't want to do. This would be one more little label to put on the infocard and would do almost nothing to game speed.
<1500: Fresh (default stats)
<4000: Veteran (+3.333% stats)
<6000: Elite (+6.667% stats)
>=6000: Legendary (+10% stats)
All the numbers are arbitrary, but I think you get the idea. The more combat the thing goes through, the better it does in future engagements. It's not a huge boost, just enough that a veteran fleet is going to kill one fresh out of the gate, which is what should happen anyways. All ships have their quirks, and that's not something you'll learn in the manual. You have to get to know your ship, which is going to happen through combat.