Showing that $|\mathcal{A}| \equiv |\mathcal{N}| \mod{p}$ from the work you've already shown follows from the fact that the orbit $|O(H)|$ under the conjugation action is equal to the index of the normalizer $|G:N_G(H)|$ by the orbit-stabilizer theorem. If $H$ is not normal, then this index is a non-trivial power of $p$, and thus the order of the orbit is divisible by $p$.
The way I figured out the rest of the problem uses induction on $k$. It is somewhat involved (and I can't see a cleaner proof), so I will give a sketch.
For $k=1$, I use a different method. Partition $G$ via the equivalence $g \sim g'$ if $\langle g\rangle = \langle g' \rangle$, and then counting the total modulo $p$. You need to check that each subgroup of order $p$ corresponds to an equivalence class of size $p-1$, and the only remaining equivalence class whose order is not divisible by $p$ is the equivalence class $\{e\}$ of the identity.
For the inductive step, I count (modulo $p$) the number of pairs $(P,Q)$ of normal subgroups $P,Q$ with $|P| = p^{k-1}, |Q| = p^k, P\subset Q$. Count these pairs in two ways, first by choosing $Q$ and subsequently all corresponding $P$, and second by choosing $P$ and subsequently all corresponding $Q$. You can have an equation relating the total number of $Q$ to the following:
- The total number of $P$.
- For each $P$, the number of such $Q$ containing $P$.
- For each $Q$, the number of such $P$ contained in $Q$.
Examine the sum to note that if all of these are congruent to $1$ modulo $p$, so too is the total number of $Q$. The first of these is congruent to $1$ inductively. The second is also congruent to $1$ by considering the normal subgroups of $G/P$ and using the $k=1$ case.
The third is also congruent to 1, but requires an argument. You inductively know that the number of subgroups $H\le Q$ with $|H| = p^k$ is congruent to $1$ modulo $p$, and you need to show that the number of such $H$ that are normal as subgroups of $G$ is also congruent to 1 modulo $p$. This argument uses $G$'s conjugation actions on subgroups of $Q$ and is otherwise identical to the $|\mathcal{A}| \equiv |\mathcal{N}|$ argument above.