Same issue with the Commander and Admiral ships... Early game these ships are crazy powerful. But by the time one gets to the end of the game the fleets with these leaders are actually the SLOWEST fleets, despite their ability to double movement.
Have you tried moving the Commander and Admiral ships out of the fleet and move them to a newer fleet? If you didn't already know, they are units in a fleet. In my experience, these ships are always the state of the art. I find they have at least 1 engine (warning, I favor ship capacity techs in my games). I think its the old ships that are slowing you down.
If the fleets are not fast enough, try adding another commander to the fleet. You'll need a second fleet with no commanders. You can split your fleet for this.
