Should you start a new paragraph for a new speaker if both speakers are contained in the same quoted passage?

What you call the rule is more of a convention, and can be subject to common sense. In general, if you are narrating a dialogue in a novel or short story, it makes it easier for the reader to follow what is going on. But there can be contexts in which that convention is unnecessary and may, in some contexts, be distracting.

In this case, you are quoting from the Old Testament, which is written in verses, which are preserved in the English rendition of the original Hebrew. You would find exactly the same with manuscripts of, say, Homer's Iliad or Odyssey. These are written in hexameter verse without paragraphs of any kind. But the same is true of John Milton's Paradise Lost.