They are both common enough in spoken and written English. "all of a sudden" has more of an emotive "story-telling" feel that may not be suitable in more objective or formal contexts.
New words, one handy idiom, and a 2-minute quiz — delivered to your inbox to keep your streak alive.