Decay of real continuous algebraic functions at infinity

Update: As pointed out by Igor, this is not convincing. I only show that if $p(x,f)=0$ and $p(x,0)\not=0$ for $|x|>R$, then the claim holds. However, the OP only assumes that $f\not=0$ for $|x|>R$ (I mixed up the two originally).

Original answer: Yes, this works. If we had $|f(x_N)|\lesssim |x_N|^{-N}$ for arbitrarily large $N$, then the constant coefficient $p=a_0$ in the equation $\sum a_jf^j=0$ solved by $f$ would have the same property.

So it suffices to show that if a polynomial satisfies $p(x)>0$ for $|x|>R$, then in fact $|p(x)|\gtrsim |x|^{-N}$ for some $N$. This follows from the Positivstellensatz, which says, in our setting, that $$ p(x) = \frac{1 + (|x|^2-R^2)F(x)+G(x)}{(|x|^2-R^2)H(x)+K(x)} \ge \frac{1}{(|x|^2-R^2)H(x)+K(x)} \gtrsim |x|^{-N} ; $$ here, $F,G, H, K$ are sums of squares of polynomials.

(I suspect there must be a much more elementary argument.)

Well it's true in dimension $1$, and I think the following argument should reduce the case $n>1$ to the $n=1$ statement.

Let $r_0 = \max_{f(x) = 0} \| f(x) \|$. Then $f$ has constant sign on $\| x \| > r_0$ (continuous function on a connected set), and we may assume the sign is positive (else replace $f$ by $-f$). For $r \geq r_0$, define $$ F(r) := \min_{\|x\| = r} f(x). $$ This is an algebraic function of $r$ because it is the value of the algebraic function $f(x_1,\ldots,x_n)$ on the algebraic variety (typically a curve) in ${\bf R}^{n+2}$ specified by the following equations on $r$, $x_1,\ldots,x_n$, and $c$: $$ \sum_{i=1}^n x_i^2 = r^2, \quad \forall i: \frac{\partial f}{\partial x_i} = c x_i. $$ But by hypothesis $F(r) \neq 0$ for $r > r_0$, so there exists $N<\infty$ such that $f(r) \gg |r|^{-N}$ for large r, as claimed.

Your function $f$ is, in particular, a continuous semi-algebraic function on $\mathbf R^n$, i.e., its graph is a semi-algebraic subset of $\mathbf R^{n+1}$. Such functions are known to have sub-polynomial growth. More precisely (cf. Bochnak, Coste, Roy: Real algebraic geometry, Proposition 2.6.2, p. 43):

Let $S\subseteq\mathbf R^n$ be a closed semi-algebraic subset, and let $f\colon S\rightarrow \mathbf R$ be a continuous semi-algebraic function. Then there are $c\in\mathbf R$ and $N\in\mathbf N$ such that $$ |f(x)|\leq c(1+||x||^2)^N $$ for all $x\in S$.

Apply this to the inverse $1/f$ of your function on the closed semi-algebraic subset $||x||\geq A$, where $A\in\mathbf R$ is such that all zeros of $f$ have norm $<A$.