I finally managed to somewhat address this.
You would now lose ~15 ships on the 1st round, and 2 more on the 2nd round - that's with all your ships fully cloaked at battle start.
I changed the way combat is handled a bit by making civs take turns to fire the weapons of each of their ships, but still governed by initiative. I also made scouts and non-combat ships have their initiative halved - mostly to make (most) warships fire before scouts (it could decrease the effects of the change).
Now, this needs extensive testing (in both small and large battles) to see if it doesn't break anything; and to see if it is actually better overall. Please report!
I'll release a new patch shortly, with some other changes too.