Using private methods for decreasing CC by refactoring some decision points into separate methods decreases the CC of the actual method and eases reading, but does not decrease the effort to get full branch coverage in testing.
Is this justifyable? What is you field experience?
Sometimes, making your application code less complex and more readable has as a consequence that your test code becomes more complex and less readable. However, that is not a reason not to do the refactoring. Readability of the production code is more important than your tests.
If you make some methods private for decreasing CC and improving readability, you could use a framework like Mockito to still be able to test the private methods themselves.