You are using the word "literally" correctly. The reason it sounds clunky is that lately people use "literally" as throwaway hyperbole. It's the same as with the word "hilarious": if everyone describes everything remotely humorous as "hilarious", it robs the original word of vigor.
Your choice then is to make a stylistic substitution. Would your sentence sound less clunky to you if you used a less specific word, like "completely" or "thoroughly"? Would it sound better to you if you dropped the adverb altogether and just left "at a loss for words" carry some subtler meaning? Would it sound better to you to change the whole sentence for something else, like "struck silent" or "left speechless"? It's ultimately a choice only you can make.