You might be looking for directly related or lineally descended or some variation thereof (lineage, for example).
direct adj. definition 2b:
being or passing in a straight line of descent from parent to offspring : lineal
<direct ancestor>
lineal adj.
having a direct family relationship : related by a direct series of parents and children
All links/quotes are from Merriam-Webster.
So, for you example of "John and Paul are x", x could be "directly related" or "lineally related" or "of the same lineage". I think directly related would be the most easily understood, though to be 100% clear, I'd actually phrase it like "John is a direct descendant of Paul" (or "Paul is a direct ancestor of John"). Lineally does actually have precisely the definition you want, but it's not a commonly-used word, and while most people could figure out its meaning based on "line", to a math person like me, it always at first looks like a misspelling of linearly. :)