The Axiom of Choice is that I can have an infinite number of sets and I can "choose" a value from each of them. A choice from a set is basically what a bit is (give or take the question of probabilistic weighting of the values in the set, which is important in the finite case but can't save you in this case so it's a distraction here). Invoking the Axiom of Choice, which is only interesting in the infinite case, is injecting an infinite number of bits into the proof that uses it, as it involves an infinite number of choices.

At best the invocation has an acceptance procedure, but it does not come with a procedure for making the choice. Probably in most cases it doesn't even have an acceptance procedure, which is to say, if we were presented with the choices (or a finite subset of them, since we can't handle the infinite set) we couldn't even tell if they are "correct". So it is not the case that it's just like the primes case, which I mentioned is distinctly finite in bits even if the set is infinite in cardinality. The Axiom of Choice is an infinite (even uncountably infinite or more) number of selections with no way given of representing that in any finite manner. In many cases the Axiom of Choice is invoked when we can't even define the sets we are choosing from, if not most or all of them.

So, from my computer science, information theory point of view, proofs involving the Axiom of Choice are proceeding along nicely, finite statement here, finite statement there, finite logic done on these finite statements, everything's all nice and finite and comprehensible and then BANG an infinite number of unknownable bits are dumped on me, and then we proceed along like nothing weird has happened and do some more finite logic on finite values based on this infinite pile of unknownable bits. It is what it is, but what it is is strange. I mean, it's not news to mathematicians that it can be a bit strange, but I think this "infinite number of bits" is one of the better ways to see how strange it is.

Another way to look at it is, the AoC is generally invoked without even a theoretical decision procedure to make the choices. It just has a demonstration that such a choice exists. So it amounts to "and then god chooses a value in these sets for us in accordance to our criteria". Lowercase on purpose. A more conventional term in computer science is "oracle". Every invocation of the AoC is basically adding this mathematical entity of such incredible power that we can't determine anything about how it does its thing, or whether or not it is correct. Again. Legal. But something I think is taken more casually than I would like, and I think doing mathematics without scattering infinitely knowledgeable (if only in very constrained ways) and powerful oracles around everywhere with the same casualness as one might do a disjunction or implication in all our proofs is underrespected as a discipline within mathematics in general.