Hamlet is actually describing what is a common experience. We have all had moments of insight in which we realized that something we only felt or sensed was a glaring and sometimes menacing reality. We pick up clues intuitively, but it often takes time, or some new development, for the truth to break through into our consciousness. Here is how Henry James describes this truly very common experience in his excellent short novel Washington Square:

A sudden fear had come over her [Catherine Sloper]; it was like the solid conjunction of a dozen disembodied doubts, and her imagination, at a single bound, had traversed an enormous distance.

Hamlet had been sensing that there was something more to his father's death, his uncle's coronation, and the marriage of his uncle and his mother than had been thoroughly explained. There may have been many clues he picked up intuitively but hadn't pieced together into a picture until the Ghost gave him the one missing piece of the puzzle. For example, his uncle and mother were showing unusual concern about what he was thinking and feeling. Claudius was acting much differently than his uncle had acted in the past, and the new king was doing an unusual amount of drinking. The story about a serpent killing Hamlet's father was fishy enough in itself. Such a thing might happen in India or Borneo, but how often do poisonous snakes kill people in a cold climate like Denmark's? In fact, are there any poisonous snakes in Denmark at all? 

Hamlet is sincerely overwhelmed with grief at the death of his father. He is also disgusted with his mother. He has plenty of things to occupy his mind without focusing on his feelings, or suspicions, or vague intuitions, about Claudius. Hamlet might have picked up clues long before his father's death that would make him sense that his uncle might be sexually attracted to Gertrude and might have sinister ambitions. Our unconscious minds will often give us warnings in our dreams. It might be said that we all have "prophetic souls," but most of us often fail to heed them. This, in fact, was true of Hamlet. He was all wrapped up in his studies of languages, ancient history, and philosophy at Wittenberg and didn't pay attention to practical matters at home. Otherwise, he might have become king instead of his wicked and cunning uncle.

Hamlet has been uneasy about Claudius' assention to the throne and his over-hasty marriage to Gertrude.  Hamlet has a prophetic soul to the extent that he has not liked Claudius from the start of the play, so hearing that Claudius murdered King Hamlet was not that big of a surprise.   I don't think he suspected him of murder -- no one suspected murder.  The ghost says that the story was out that serpent bit Claudius in the ear while he was sleeping in the garden.  I don't think there was any thing else suspected by anyone in the court.  There is no mention of an investigation or anything like that.  Claudius has control of the court as we see in his first monologue in Act 1 Scene 2. 

Hamlet meets the ghost for the first time in this scene, and the ghost tells Hamlet that Claudius, Hamlet's uncle, killed Hamlet's father. Hamlet's response to finding out that his uncle killed his father is, "O my prophetic soul!/Mine uncle!". Hamlet had suspected that Claudius had something to do with his father's death all along. So when he refers to his "prophetic soul", he means that deep down inside, he knew his uncle was guilty of the murder of his father. "Prophetic" means predictive of something to come, and Hamlet's "soul", the very essence of him, was trying to tell him that Claudius is guilty. The soul is personified since it's given the human action of prophecy.