You should scramble a 5x5 using 3x3 scrambles, and practice that. An avg. of 12 or even an avg. 50 would help a lot. If you avg. 16 on a regular and it takes you 35-45, you can easily cut 10-15 seconds off that.Thanks ! About the 3x3 part, I average ~16s on the 3x3 but it takes me between 35s and 45s to do the same on the 5x5. I still have some recognition problem for some OLLs on bigcubes.
Another thing I noticed, when I started "serious" training for the 4x4 and 5x5 3 weeks ago, I first did one week of 4x4 and then one week of 5x5. During theses weeks, my times really dropped. Now I switch every day between 4x4 and 5x5 and it seems that my times doesn't drop anymore.
Do you think I should keep the same cube size for a week before switching to the other ?
As for what cube, I'm not sure. I don't practice as much now as I used to, but I used to do avg's on 4x4, and then go straight to 5x5 after, and my times continually dropped. Although you will get stuck as different times. Keep practicing and you'll get through it.