In general the answer to the question would be yes, and many people do so, both by staying at the same institution and by changing universities. But there are caveats. It probably isn't the norm, and there may be local traditions, say in Brazil, that suggest it is a poor idea. But you would probably already know if that were true.
There are many reasons to change advisors beyond a poor experience. One of the main ones is that the student wants to change sub-fields and another faculty member would be more appropriate. It might also be desirable to move to a more senior faculty member for a variety of reasons. An untenured advisor can be risky since their main focus will necessarily be on their own work.
I don't actually think there is a need to explain it. Certainly you don't need to say that you haven't been happy. If pressed, just say that you've decided that the other person would be more appropriate.
I also doubt that you need a "gap".
But find another person and get their agreement to take you on before you make any waves.