Assuming that the first  : (colon) is the separator between the "key" and "value" parts of a record (needs Perl version 5.10+ for  \K operator):

c:\@Work\Perl\monks>perl -wMstrict -le
"use 5.010;
 ;;
 my @ra = (
   'session-redis-hosts-fault-tolerant: \"tyk-redis-1.gateways.svc.clu
+ster.local,tyk-redis-2...\"',
   'message-center-db: \"http://message-center-db-1b.message-center-db
+.svc.cluster.local\"',
   'a-b-c:d-e-f:g-h-i:j-k',
   );
 ;;
 for my $s (@ra) {
   print qq{'$s'};
   $s =~ s{ \G [^:]*? \K - (?= [^:]* :) }{_}xmsg;
   print qq{'$s' \n};
   }
"
'session-redis-hosts-fault-tolerant: "tyk-redis-1.gateways.svc.cluster
+.local,tyk-redis-2..."'
'session_redis_hosts_fault_tolerant: "tyk-redis-1.gateways.svc.cluster
+.local,tyk-redis-2..."'

'message-center-db: "http://message-center-db-1b.message-center-db.svc
+.cluster.local"'
'message_center_db: "http://message-center-db-1b.message-center-db.svc
+.cluster.local"'

'a-b-c:d-e-f:g-h-i:j-k'
'a_b_c:d-e-f:g-h-i:j-k'
[download]

Update: Actually, the look-ahead portion of
    $s =~ s{ \G [^:]*? \K - (?= [^:]* :) }{_}xmsg;
seems unnecessary. Changing the first inverted character class to  [^:-] is simpler:
    $s =~ s{ \G [^:-]* \K - }{_}xmsg;