Yes, you definitely need a new paragraph every time there's a change in speaker. That signals to the reader that a new person is talking and can help the reader keep track of who is speaking. It can be confusing if you have more than one person speaking within the same paragraph.
Grab a novel off your bookshelf ... any novel ... and you'll see exactly what this should look like.
