Unless the surface through which you're calculating the flux is closed (in which case the canonical choice is to choose the area vector outward, you choose the direction of the area vector $\hat{A}$. There's no rule, here; you just need to be consistent throughout the whole calculation. You'll find that the choice doesn't affect any physical consequences. A standard choice is to choose $\vec{A}$ so that the flux is positive. This makes reasoning with Lenz's law easier.
Note that the right-hand rule just doesn't apply for this calculation: you're computing a dot product, not a cross-product. Later on, you might need to use the right-hand rule to figure out the direction of the induced current, but that's not a part of the calculation of the flux.
To be a little more careful about this. Faraday's Law states that a changing magnetic flux induces an emf, mathematically given by
$$
\textrm{emf} = \oint_C \vec{E}\cdot d\vec{s}=-\frac{d}{dt}\int_S\vec{B}\cdot d\vec{A} = -\frac{d\Phi_{\textrm{mag}}}{dt}\,,
$$
where the curve $C$ is the boundary of the surface $S$, oriented according to the right-hand rule. Which is to say, you choose an orientation for the surface $S$, point your thumb along this direction, and your fingers then curl in the direction along which we're integrating along $C$.
You can choose any orientation for the surface $S$ as long as you consistently choose the integration direction along $C$.
Now, often in practice, we compute the absolute value of the right-hand side of Faraday's Law to get the magnitude of the induced emf, and we use Lenz's Law to figure out the direction of the induced electric field, induced current, and/or induced magnetic field. This separates the calculation into two pieces which makes it easier.