You can determine the number of 5 minutes slots between your min and max time, and choose one of these slots randomly.

For the output, use the strftime method to get any format you want:

import datetime
import time
import random

MINTIME = datetime.datetime(2020,7,1,0,0,0)
MAXTIME = datetime.datetime(2020,7,31,0,0,0)

mintime_ts = int(time.mktime(MINTIME.timetuple())) #convert date into int
maxtime_ts = int(time.mktime(MAXTIME.timetuple())) #convert date into int

nb_slots = (maxtime_ts - mintime_ts)//(5*60)  # number of 5 minutes slots
for RECORD in range(10):
    random_slot = random.randint(0, nb_slots)
    random_ts = mintime_ts + 5*60 * random_slot
    RANDOMTIME = datetime.datetime.fromtimestamp(random_ts)
    print(datetime.datetime.strftime(RANDOMTIME, '%H:%M'))
    

Output:

11:20
15:20
11:25
02:10
13:30
08:30
00:45
06:10
17:05
01:00

import datetime
import time
import random

MINTIME = datetime.datetime(2020,7,1,0,0,0)
MAXTIME = datetime.datetime(2020,7,31,0,0,0)

mintime_ts = int(time.mktime(MINTIME.timetuple())) #convert date into int
maxtime_ts = int(time.mktime(MAXTIME.timetuple())) #convert date into int

scale = 5*60

for RECORD in range(100):
    random_ts = random.randint(mintime_ts//scale, maxtime_ts//scale)*scale
    RANDOMTIME = datetime.datetime.fromtimestamp(random_ts)
    print(RANDOMTIME.strftime('%H:%M'))

You are storing the time in seconds, so you could simply divide mintime_ts and maxtime_ts by 300 (60*5) and then multiply the result from randint back by 300.

With this, you are randomly selecting a 5 min timestamp between the min and max you defined.

random_ts = random.randint(mintime_ts//300, maxtime_ts//300)*300

For the formatting part, you can use datetime's strftime

print(RANDOMTIME.strftime("%H:%M"))

Sidenote: You can also use random.choices to sample random numbers with replacement (meaning that the number can be selected more than once). The advantage is that you can tell the function to give you all the numbers you want at once.

random.choices(
    # Define the population of numbers you want it to select from.
    # In your case this is any number that is a multiple of 300 (because of the 5 min)
    population=range(mintime_ts//300*300, maxtime_ts, 300),
    k=100 # Define how many numbers you want
)

Using pandas

In [15]: import pandas as pd

In [16]: [i.strftime("%H:%M") for i in pd.date_range("01:13", "01:57", freq="5min").time]
Out[16]:
['01:13',
 '01:18',
 '01:23',
 '01:28',
 '01:33',
 '01:38',
 '01:43',
 '01:48',
 '01:53']

You need not to use datetime functions, just use random functions for generate random integers in specified interval:

import random

for RECORD in range(100):
  print(
    #generate random int between 0 and 23 convert to string and pad by '0'
    str(random.randint(0,23)).rjust(2,'0') 
    # add devider
    + ':' + 
    # random int between 0 and 55 with step 5
    str(random.randint(0,11)*5).rjust(2,'0') 
  )

The following should help:

#Necessary packages

import datetime
import random
import numpy as np

#Define the minute range (0-55, 60 means 0) with step-size of 5

minute_range = np.arange(0,59,5)

#Define the hours range (0,23, 24 means 00)

hour_range = np.arange(0,24,1)

#randomly pick hour and minute and convert it into time object

a = datetime.time(random.choice(hour_range),random.choice(minute_range))

#convert the object to string

print(a.strftime("%H:%M"))

a loop to serve as the demonstration:

for _ in range(5):
    a = datetime.time(random.choice(hour_range),random.choice(minute_range))
    print(a.strftime("%H:%M"))

#Output:

05:25
09:55
07:05
08:05
11:05

I hope I could help.