Let $n$ be the degree of $f$, so the order is a divisor of $p^n-1$. As the computation of powers in $E$ is a cheap operation, I believe the following could be suitable: If $\alpha^m=1$, then check if there is a prime divisor $r$ of $m$ with $\alpha^{m/r}=1$. If not, then $m$ is the order, and if yes, then set $m=m/r$ and repeat the process.
Start the whole thing with $m=p^n-1$.
Probably there are better ideas, but I cannot think of one.
I can show that exceptions occur at most for $n=3$. (Primality of $n$ is never used.)
Since $n$ is odd, $\mathbb F_{q^{2n}} = \mathbb F_{q^2} \otimes_{\mathbb F_q} \mathbb F_{q^n}$. The trace map $\operatorname{Tr}:\mathbb F_{q^{2n}} \to \mathbb F_{q^2}$ is obtained by tensoring the identity map $\mathbb F_{q^2} \to \mathbb F_{q^2}$ with the trace map $\operatorname{tr} : \mathbb F_{q^n} \to \mathbb F_q$.
Thus, choosing an arbitrary basis of $\mathbb F_{q^2}$, we can write any $a$ as a pair of elements $a_1,a_2 \in \mathbb F_{q^n}$, and your condition that $y \in \mathbb F_{q^n}$ satisfies $\operatorname{Tr}(y)\neq 0$ but $\operatorname{Tr}(ay)=0$ is equivalent to the condition that $\operatorname{tr} (y) \neq 0$ but $\operatorname{tr} (a_1 y ) =\operatorname{tr}(a_2 y)=0$. (We can ignore the condition that $y\neq 0$ as it is implied by the condition that $y$ has trace zero.)
Since the trace map of a product is a perfect $\mathbb F_q$-linear pairing on $\mathbb F_q^n$, such a $y$ exists unless $1$ is an $\mathbb F_q$-linear combination of $a_1$ and $a_2$.
I will show there must exist a member of $\mathcal A$ that has this unusual property by bounding the number of members of $\mathcal A$ that do have this unusual property.
Note that every member of $\mathcal A$ is in the subgroup of order $q^n+1$, thus has norm to $\mathbb F_{q^n}$ equal to $1$. This is a nonsingular quadratic equation in $a_1,a_2$. For each $\lambda_1,\lambda_2$ in $\mathbb F_q$, not both zero, $\lambda_1 a_1 + \lambda_2 a_2 =1$ is a linear equation. There can be at most two solutions to a linear equation together with an nonsingular quadratic equation in two variables, since it gives a nontrivial quadratic equation in one variable.
Summing over possible choices of $\lambda_1,\lambda_2$, the number of members of $\mathcal A $ with this unusual property is at most $2 (q^2-1)$. So we can only have all members of $\mathcal A$ with this property if
$$ \frac{q^n+1}{q+1} \geq 2 (q^2-1)$$
i.e.
$$q^n+1 \geq 2 (q^2-1) (q+1).$$
For $n\geq 5$, the left side dominates the right side for any $q$.
Best Answer
See for example https://en.wikipedia.org/wiki/Conway_polynomial_(finite_fields). There is plenty of theory and practice in the area, going back to Richard Parker.