(Not an answer, but too long for a comment)
One way to look at what you're asking for is a theory in some appropriate language which axiomatizes that we have a serial directed rooted graph, and a collection of subsets of the graph which behaves like $N(\mathcal{G},s)$, where the part of the axiomatization that dictates the behaviour of $N(\mathcal{G},s)$ doesn't say anything about the graph relation on $\mathcal{G}$. I'll give an axiomatization where the part that talks about $N(\mathcal{G},s)$ does mention the graph relation, and I'll set it up in such a way that it'll seem unlikely that it can be redone without mentioning the graph relation. I'm not sure about this, it's just an idea, but it's too long for a comment.
The Language
Consider the language $(\bar{V}, \bar{N}, \bar{E}, \bar{s}, \bar{\epsilon})$ - two unary relation symbols, one binary relation symbol, one constant symbol, and another binary relation symbol, respectively. I'm going to set up a theory whose finite models will be precisely (sort of) those in which $(\bar{V}, \bar{E})$ is interpreted as a directed serial graph $\mathcal{G}$, $\bar{s}$ gets interpreted as a member $s$ of $\bar{V}$, $\bar{N}$ gets interpreted as $N(\mathcal{G},s)$, and $\bar{\epsilon}$ gets interpreted as the membership relation, a subset of $\bar{V} \times \bar{N}$. Setting up the right theory is easy, the only part that will require a little explanation is how we ensure $\bar{N}$ gets interpreted correctly.
Axiomatizing $N(\mathcal{G},s)$ when we're allowed to mention the edge relation
Consider a formula like:
$$x_1 = \bar{s} \wedge x_1 \neq x_2 \wedge x_1 \neq x_3 \wedge x_2 \neq x_3$$
$$\wedge \bar{E}(x_1,x_2) \wedge \bar{E}(x_2,x_1) \wedge \neg \bar{E}(x_1,x_3) \wedge \neg \bar{E}(x_3,x_1) \wedge \neg \bar{E}(x_2,x_3) \wedge \neg \bar{E}(x_3,x_2)$$
It "says" we have three distinct $x_i$, the first one is $s$, and it tells you exactly which pairs stand in edge relation to one another and which don't. You can also tell by looking at it that it defines a set $\{ x_1, x_2, x_3\}$ which contains an infinite path starting at $s$, namely $x_1, x_2, x_1, x_2, \dots$.
Let's define $\mathcal{R}$ to be the set of formulas in the language $(\bar{s}, \bar{E})$ of the form $\phi(x_1, \dots , x_n)$ which say that the $x_i$ are distinct, and which tell you precisely which pairs of the $x_i$ stand in $\bar{E}$ relation to one another, and which don't. Define $\mathcal{R}^+$ to be those formulas $\phi \in \mathcal{R}$ such that for any rooted directed graph $((V,E),s)$, we have that:
$(V,s,E)\vDash \phi(v_1, \dots , v_n) \rightarrow \{v_1, \dots , v_n\} \in N((V,E),s)$.
$\mathcal{R}^-$ will be those $\phi$ such that:
$(V,s,E)\vDash \phi(v_1, \dots , v_n) \rightarrow \{v_1, \dots , v_n\} \not\in N((V,E),s)$.
Alright, now here's our theory:
- (Rooted serial directed graph) $\bar{V}(\bar{s}) \wedge \forall x \bar{V}(x) \rightarrow [\neg \bar{E}(x,x) \wedge \exists y (\bar{V}(y) \wedge \bar{E}(x,y))]$
- (Schema for what goes in $N$) As $\phi(x_1, \dots ,x_n)$ varies over $\mathcal{R}^+$: $\forall \vec{x} \exists Y \forall x \left (\phi(\vec{x}) \rightarrow \left[ \bar{N}(Y) \wedge \bigwedge _i (x_i \bar{\epsilon} Y) \wedge \left (x \bar{\epsilon} Y \rightarrow \bigvee _i (x = x_i)\right )\right ]\right )$
- (Schema for what stays out of $N$) As $\phi(x_1, \dots ,x_n)$ varies over $\mathcal{R}^-$: $\forall \vec{x} \forall Y \exists x \left (\phi(\vec{x}) \rightarrow \neg \left[ \bar{N}(Y) \wedge \bigwedge _i (x_i \bar{\epsilon} Y) \wedge \left (x \bar{\epsilon} Y \rightarrow \bigvee _i (x = x_i)\right )\right ]\right )$
Checking this axiomatization works
It's clear that if $\mathcal{G} = (V,E)$ is a finite directed serial graph and $s \in V$, then $(V,N(\mathcal{G},s),E,s,\in)$ is a model of this theory. Conversely, if we have a finite model $(V,N_0,E,s,\epsilon)$ of this theory, then $(V,E)$ forms a directed serial graph with $s \in V$. Now let $N_1$ consist of those $Y \in N_0$ such that $\forall x (x \epsilon Y \rightarrow V(x))$. I claim that:
$N((V,E),s) = \{ \{x : x \epsilon Y\} : Y \in N_1\}$
But I won't prove this.
A remark about some "unnaturalness"
It should seem like I could have done things differently so that things looked more natural and the above claim could be proved more easily. The way I've written 2 and 3 are not the most natural, but I've done it for a reason. 2 says that if $\vec{x}$ is a tuple which is sure to contain an infinite path starting at $s$, then there's a member of $N$ consisting precisely of the members of $\vec{x}$. 3 says that if $\vec{x}$ is sure to not contain an infinite path starting at $x$, then there's nothing in $N$ consisting precisely of the members of $\vec{x}$. The formulas in 2 and 3 are in prenex normal form, where the matrix is a conditional where the left side only involves the symbols $\bar{E}$ and $\bar{s}$, and the right side only $\bar{N}$ and $\bar{\epsilon}$. Moreover, the antecedents have variables $\vec{x}$ and the consequents have variables $\vec{x}, Y, x$.
The point
You want a theory equivalent to axiom 1 and schemas 2 and 3 above, but you want to replace 2 and 3 with (probably finitely many) axioms which don't mention the symbol $\bar{E}$. I feel like there ought to be some interpolation-type theorem (along the lines of Craig Interpolation or Lyndon Interpolation) which says this can't happen, i.e. something which says that a theory in which each axiom mention either only $\bar{V}, \bar{E}, \bar{s}$ or only $\bar{V}, \bar{N}, \bar{s}, \bar{\epsilon}$ can't prove a theory which has axioms like those in schemas 2 or 3.
Best Answer
This is false in general. Let $X=\{1, \dots, n+1\}$, $Y=\{n+1, \dots, 2n+1\}$, and $Z$ be any $(n+1)$-subset of $[2n+1]$ not containing $n+1$. Let $\mathcal{F}=\mathcal{A} \setminus \{X,Y,Z\}$. Then for all $j \in [n]$, we may take $R_j(\mathcal{F})=[n]$, since $Y \notin \mathcal{F}$. Similarly, for all $j \in \{n+2, \dots, 2n+1\}$ we may take $R_j(\mathcal{F})=\{n+2, \dots, 2n+1\}$, since $X \notin \mathcal{F}$. Finally, we may take $R_{n+1}(\mathcal{F})$ to be the complement of $Z$, since $Z \notin \mathcal{F}$. Thus, $r(\mathcal{F}) \leq n$. This is a counterexample to your conjecture, provided $n \geq 6$.