Cardinality of algebraic extensions of an infinite field.

An exercise in Lang's algebra book is: let $k$ an infinite field, and $E$ an algebraic extension of $k$. Then $E$ has the same cardinality as $k$. How can one can prove this?

HINT: First prove that $k[x]$ and $k$ have the same cardinality, you can do that by showing that $k[x]\cong\bigcup k^n$, and by induction $k^n$ and $k$ have the same cardinality, so $|k[x]|=\aleph_0\cdot|k|=|k|$; then show there is a surjection from $k[x]$ onto $E$, and an injection from $k$ into $E$. Conclude the wanted equality.

(Note that this makes a heavy use of the axiom of choice, and indeed without the axiom of choice one might have a counterexample of an algebraic closure of the rational numbers which is not countable.)

There is a canonical map $\operatorname {minpol}:E\to k[X]$ sending an element $e\in E$ to its minimal polynomial $\operatorname {minpol}_e(X)\in k[X]$ over $k$.
Since the image $\operatorname {minpol}(E)\subset k[X]$ contains all the affine polynomials $X-q \;(q\in k)$, that image $\operatorname {minpol}(E)$ has the same cardinality as $k$ (since $k$ and $k[X]$ have same cardinality, as already remarked by Asaf).
Since the fibers of $\operatorname {minpol}: E\to \operatorname {minpol}(E)$ are finite and non empty, the set $E$ also has the cardinality of $k$, as desired.