Does existence of a non-continuous linear functional depend on Axiom of Choice?

You do not need the axiom of choice to prove "There exists a normed space with a discontinuous linear functional". Consider the space $c_{00}$ of all sequences of real numbers with only finitely many nonzero terms, with the supremum norm. The functional $f(x) = \sum_{n=1}^\infty n x(n)$ is discontinuous. Everything in this argument is completely explicit and constructive, and we needed no choice whatsoever.

You do need the axiom of choice to prove "There exists a Banach space with a discontinuous linear functional". This is nontrivial. I found a reasonable overview in C. Rosendal, "Automatic continuity of Polish group homomorphisms", Bull. Symbolic Logic 15 (2009), no. 2, 184-214.

Very roughly: It is not hard to show it suffices to consider the case of a separable Banach space $X$, which is a Polish space (separable and completely metrizable). A subset $A$ of a Polish space has the property of Baire if it can be written $A = U \Delta M$ where $U$ is open and $M$ is meager. A function between Polish spaces is Baire measurable if the preimage of every open set has the property of Baire. There is a short but clever argument known as the Pettis lemma that shows that any linear functional on $X$ which is Baire measurable must in fact be continuous. Then, there is a deep result of Shelah and Solovay which says that it is consistent with the negation of the axiom of choice that every subset of every Polish space has the property of Baire. If so, then every function on $X$ is Baire measurable, and every linear functional on $X$ is therefore continuous.