Parsing random phrases from a file
I'm no expert in performance optimization or even threads, so my code review will mostly be some style suggestions, but I do have suggestions how I would implement the the phrase building to be faster - purely from my gut :-)


A nitpick at the beginning: You should try and clean up your indentations. They are all over the place and make reading the code a bit more difficult
You should declare variables to use interfaces where appropriate instead of concrete class. That makes the code more flexible for example in case you get the keys for a different source. In your case declare your map as Map&lt;String,List&lt;String&gt;&gt;.
Avoid global variables. If would be better to have addKeys return the map (and thus be renamed readKeys) and pass it on to parseString as an argument.
In the main function a for loop is probably more appropriate instead of the while.
Try to get rid of the duplicate scan.nextLine(); in the inner while loop, by moving the exiting condition inside the loop.


Now to optimizing the phrase building. There are two main points I would consider here:


Avoid copying data. Currently you convert your string with the placeholders into a StringBuilder and insert the text in place of the placeholder. Both creating the StringBuilder and inserting into them requires allot of data copying internally. 
Don't repeat the parsing of the placeholder text. Instead I would parse the text once into a data structure and then generate the random phrases using that structure.


I could write some (pseudo) code to demonstrate, what I mean, but you should be writing it yourself, so I'll wait and see, if you can come up with an implementation based on those two points.