We propose a test of the conditional independence of random variables $X$ and~$Y$ given~$Z$ under the additional assumption that $X$ is stochastically nondecreasing in~$Z$. The well-documented hardness of testing conditional independence means that some further restriction on the null hypothesis parameter space is required. In contrast to existing approaches based on parametric models, smoothness assumptions, or approximations to the conditional distribution of $X$ given $Z$ and/or $Y$ given $Z$, our test requires only the stochastic monotonicity assumption. Our procedure, called \textnormal{\texttt{PairSwap-ICI}}, determines the significance of a statistic by randomly swapping the $X$ values within ordered pairs of~$Z$ values. The matched pairs and the test statistic may depend on both $Y$ and $Z$, providing the analyst with significant flexibility in constructing a powerful test. Our test offers finite-sample Type~I error control, and provably achieves high power against a large class of alternatives. We validate our theoretical findings through a series of simulations and real data experiments.