Here are a few pointers in winning Random Battles : 

1. Use Magic. Many monsters are vulnerable to a certain type of magic. For example, use Ice spells against Goblins, Fire against Skeletons, Bolt against Pisco Demons.

2. Most of the monsters appear only in random battles, for example, there are no Gull or Squid type monsters in story battles. Bring a mediator, you never know what monster you'll encounter.

3. Kill all but one enemy, make sure it cannot cause any status problems, hit it a bit, heal it, heal yourself, continue till you get the desired amount of JP for certain costy abilities.

4. As Ramza's level goes up, so do the monsters, be careful.

5. Some battlefields may sometimes hold an enormous amount of enemies. In Grog Hill, it is possible to encounter 11 monks ! Good luck in dealing with them....

6. Use distant attacks if you can ( Guns, Bows, Magic, Summons, etc.... ), they'll protect you from stronger monsters.