I'm not sure how the admiral is being tracked in the game. You can check some individual traits of boat captains though. A bunch of mine have "sea sickness" for no apparent reason. This could be resulting in "negative command." I've been disbanding ones like that when they deplete rather than re-training. Try to cull out any losing admirals or ones with bad traits, they don't seem to get stars after that (at least it becomes much more difficult even if they win.)

Once your admiral gets a few wins and his boats have some chevrons, they get pretty tough, even on VH/VH. I am using small fleets as Carthage and only biremes so far, but I've been exerting some naval muscle recently to clear the waters for my Roman invasion. I now have two fleets of two and three boats with 3 and 4 stars respectively. It is nice to be able to actually fight meaningful naval campaigns. The Gauls, Romans, and Numidians have all been blockading my ports regularly, I ignored them for awhile but I finally had to take them on at sea, systematically hunting down and killing the small fleets far from their home ports.