As Sam Hopkins commented, 8 vertices are enough. Let $Q$ be the pentagon from the picture and let $\pi$ be the plane containing it. Now we can define the triangle $P$ as a triangle of less diameter than the black segment and intersecting $\pi$ at two points: one point $a_0$ in the open blue region $B$ and one point $b_0$ in the open green region $G$. $P$ and $Q$ are not linked, and it is intuitively clear that they are interlocked, but let´s prove it in detail.
Suppose there is a path of triangles $P_t=i_t(P)$ going to infinity, such that $P_t$ is disjoint with $Q$ for all $t\in[0,\infty)$ and $i_t:P\to\mathbb{R}^3$ is a continuous path of isometries (continuous in the supremum norm for functions $P\to\mathbb{R}^3$) with $i_0=Id_P$. Let´s try to derive a contradiction.
Lemma 1: Let $i$ be an isometry such that $i(P)$ intersects $\pi$ at exactly two points $a,b$. Then $\forall\varepsilon>0\;\exists\delta>0$ such that for any isometry $j$ with $d(i,j)<\delta$, $j(P)$ intersects $\pi$ at two points $a',b'$, with $d(a,a')<\varepsilon$ and $d(b,b')<\varepsilon$.
Proof: First of all, if $d(i,j)$ is small enough, $j(P)$ will intersect $\pi$ in two points, because the images by $j$ of at least two vertices of the triangle will be outside $\pi$.
Now consider the function $F(x,y)=$ intersection of the line passing through $x,y$ and $\pi$, defined in an open subset of $\mathbb{R}^6$. This function is continuous in its domain.
Suppose $a$ is not a vertex of the triangle. Then it is in the edge formed by two vertices $i(v_1),i(v_2)$, each in one half space of $\pi$. By continuity of $F$, if $d(i,j)$ is small enough we have a point $a'=F(j(v_1),j(v_2))$ in $j(P)$ at distance $<\varepsilon$ of $a$.
So the lemma works when $a,b$ are not vertices of the triangle. $a$ and $b$ cannot both be vertices of the triangle, so suppose $a$ is a vertex, $a=i(v_1)$ with $v_1$ a vertex of $P$, and $b$ is not. Then for $d(i,j)$ small enough both $F(j(v_1),j(v_2))$ and $F(j(v_1),j(v_3))$ will be at distance $<\varepsilon$ from $a$, so the one which is in $j(P)$ will be the point $a'$. $\square$
Now that we are done with the lemma 1, we can define
$$k=\sup\{t>0;P_s\textit{ intersects $\pi$ at two points, one in $B$ and one in $G$, }\forall s\in[0,t)\}.$$
Lemma 2: $k>0$, and in $[0,k)$ there are paths $a_t$, $b_t$ such that $\{a_t,b_t\}=P_t\cap A\;\forall t<k$.
Proof: By lemma 1, there is some $\varepsilon>0$ such that $\forall t\in [0,\varepsilon)$, $P_t\cap A$ consists on two points, one in $G$ and one in $B$, so $k>0$. Let $a_t$ be the point in $B$ and $b_t$ be the point in $B$. By lemma 1 again, $a_t$ and $b_t$ are continuous in $[0,\varepsilon)$. Now consider the maximum $\varepsilon$ such that the $a_t$ and $b_t$ are defined in $[0,\varepsilon)$. Then $\varepsilon=k$, because if not, by the same argument using lemma 1, $a_t$ and $b_t$ will be defined in a neighborhood of $\varepsilon$.$\square$
Now let´s see that $P_k$ has to intersect $Q$, leading to a contradiction. First of all, $P_k$ has to intersect $Q$ in at least two points, one point $a_k\in\overline{B}$ and one point $b_k\in\overline{D}$. To prove this, let $t_n$ be an ascending sequence, $t_n\to k$, such that $a_{t_n}$ is convergent. Call $p_n=i_{t_n}^{-1}(a_n)$, we can suppose that $p_n$ converges to some point $p\in P$ after taking a subsequence. Finally, we can let $a_k$ be $i_k(p)=\lim_n i_{t_n}(p_n)$, and similarly with $b_k$. Now we can consider two cases:
If $P_k$ intersects $\pi$ only at $a_k$ and $b_k$ we cannot have $a_k\in A$ and $b_k\in B$: that would contradict the definition of $k$. So either $a_k\in\partial B\setminus Q$ and $b_k\in\overline{G}$ or $b_k\in\partial G\setminus Q$ and $a_k\in\overline{B}$. Both cases are impossible, because $d(\partial B\setminus Q, G)$ and $d(\partial G\setminus Q, B)$ are both bigger than the diameter of $P$.
So $P_k$ has to intersect $\pi$ in an edge. For the last time, we will consider two cases:
If $a_k$ and $b_k$ are both contained in the edge, then the edge intersects $Q$, which is a contradiction.
If not, the whole $P$ has to be contained in $\pi$. Consider an edge of the triangle containing the point $a_k$. As the edge doesn´t intersect $Q$, one of its vertices must be in $B$. There is also other vertex in $G$ (one of the vertices of the edge containing $b_k$), so the edge joining those two vertices must intersect $Q$, a contradiction.$\\[20pt]$
P.S: I had some comments regarding whether there are $P,Q$ as in the question with $7$ total vertices but they were wrong (I had not considered one case). An argument that they do not exist is given in Del's answer.
