This is true, and it follows from Serge Lang's proof of Serre's "Conjecture I" for finite fields. The analogous result is true for any perfect field $F$ of cohomological dimension $1$ by Steinberg's solution of the general conjecture.
Denote by $E_A$ the $F$-group scheme that is an affine space of dimension $\text{dim}_F(A)$ and such that $E_A(R)$ is identified with $A\otimes_F R$ for every commutative, unital $F$-algebra $R$. The subfunctor of the Yoneda functor of $E_A$ parameterizing invertible elements $u\in A\otimes_F R$ is represented by a Zariski open subset $\textbf{GL}_A$ of $E_A$, namely the inverse image of the Zariski open subset $\text{Aut}_F(E_A)\subset \text{End}_F(E_A)$ under the $F$-linear morphisms of affine $F$-spaces, $$\alpha: E_A \to \text{End}_F(E_A), \ u \mapsto (v\mapsto u\cdot v).$$
For a fixed element $b$ of $A$, consider the locally closed subscheme $C_b$ of $\textbf{GL}_A$ such that for every commutative, unital $F$-algebra $R$, $C_b(R)\subset \textbf{GL}_A(R)$ is the set of invertible elements $u\in A\otimes_F R$ satisfying $ub = bu$. The point is, there is a linear subspace $L_b \subset E_A$ parameterizing $u$ (invertible or not) such that $ub=bu$. Thus the intersection $C_b = \textbf{GL}_A\cap L_b$ is a nonempty Zariski open subset of an $F$-affine space, and thus $C_b$ is geometrically integral. By construction, $C_b$ is a linear algebraic $F$-group. Thus, $C_b$ is a smooth connected affine $F$-group.
For an element $a$ of $A$, there is a closed subscheme $T_{b,a}\subset \textbf{GL}_A$ parameterizing $v$ such that $bv = va$. As above, since this is a linear condition, it is a Zariski closed subscheme of $\textbf{GL}_A$. Assuming this is not the empty scheme, $T_{a,b}$ is a torsor for the smooth connected affine $F$-group $C_b$ via the action, $$ \mu: C_b \times_F T_{b,a} \to T_{b,a}, \ \ (u,v) \mapsto u\cdot v.$$ For $F$ a finite field, Serge Lang proved that every torsor over a finite field $F$ for every smooth connected affine $F$-group admits an $F$-point.
MR0086367 (19,174a)
Lang, Serge
Algebraic groups over finite fields.
Amer. J. Math. 78 (1956), 555–563.
http://www.jstor.org/stable/2372673?origin=crossref&seq=1#page_scan_tab_contents
For $F$ an arbitrary perfect field of cohomological dimension $1$, this was proved by Robert Steinberg.
MR0180554 (31 #4788)
Steinberg, Robert
Regular elements of semisimple algebraic groups.
Inst. Hautes Études Sci. Publ. Math. No. 25 1965 49–80.
http://www.numdam.org/item?id=PMIHES_1965__25__49_0
This is also Appendix 1 of Serre's book on Galois cohomology.
Thus the $C_b$-torsor $T_{b,a}$ has an $F$-point $v \in T_{b,a}(F) \subset A$ such that $bv$ equals $va$.
Edit. Darij Grinberg is correct that this result holds over all fields. For every infinite field $F$, the affine $F$-space $\overline{T}_{b,a} \subset E_A$ has a Zariski dense set of $F$-points. Thus, the dense, Zariski open subset $T_{b,a}$ has an $F$-point.
