animated tikzmarknode in a slide with beamer

tikzmarknode is not beamer-aware. That's an oversight, and one that I will correct in the next release. (It is, however, math-aware which means that it picks up on the math mode that it is in and implements that in the node so you don't need the dollars inside.) However, it might not be that you want a fully beamer-aware version of tikzmarknode here as it depends slightly on what you want to do with it. I suspect that what you actually want is provided by the overlay-beamer-styles library which provides ways to make TikZ styles beamer-aware. Here's an example.

documentclass{beamer}
%url{https://tex.stackexchange.com/q/593958/86}
usepackage{tikz}
usetikzlibrary{
  positioning,
  arrows,
  shapes,
  backgrounds,
  tikzmark,
  calc,
  decorations.pathmorphing,
  patterns,
  overlay-beamer-styles %% <-- use this library
}

% tikzstyle is depreciated
tikzset{
  every picture/.append style={remember picture},
  na/.style={baseline=-.5ex},
  nb/.style={baseline=10.5ex}
}



usepackage{amsmath}
usepackage[subdued]{mathastext}


begin{document}

begin{frame}

begin{equation*}
 tikzmarknode[circle,draw=red]{p}{$A$}  = B ;
end{equation*}

% To show the effect of removing the dollars
begin{equation*}
 tikzmarknode[circle,draw=red]{p}{A}  = B ;
end{equation*}

% Hide the *whole* node on slide 1
begin{equation*}
tikzmarknode[circle,draw=red,visible on=<2>]{p}{A}  = B ;
end{equation*}

% Only hide the outer circle on slide 1
begin{equation*}
tikzmarknode[circle,alt=<2>{draw=red}{}]{p}{A}  = B ;
end{equation*}


end{frame}

end{document}

Incidentally, I kept getting math overflow errors with the random steps so I removed it for this example.