My algorithm for replacing characters in string is not working

The problem is that after you've replaced the character you continue searching and may therefore replace the character you just put there. This may happen multiple times. When you find a match, you need to break out of the loop:

void replace_char(string text, string replace, string new){
    int strl = strlen(text);

    for (int h = 0; h < strl; h++){
        for (p = 0; p < 26; p++) {
            if (text[h] == replace[p]) {
                text[h] = new[p];
                break;                   // break out
            }
        }
    }
}

An even simpler version would be to just look up the character in the replacement string directly. This works if the characters in replace are in a contiguous range (and they are 26 of them as you've hardcoded):

void replace_char(string text, string replace, string new){
    int strl = strlen(text);

    for (int h = 0; h < strl; h++){
        if(text[h] >= replace[0] && text[h] <= replace[25])
            text[h] = new[text[h] - replace[0]];
    }
}

Or, make sure that replace is a contiguous range by taking the first and last character in the range instead:

#include <assert.h>

void replace_char(string text, char first, char last, string new) {
    int strl = strlen(text);

    assert(strlen(new) >= last - first);

    for (int h = 0; h < strl; h++) {
        if (text[h] >= first && text[h] <= last)
            text[h] = new[text[h] - first];
    }
}

and call it like so:

replace_char(message, 'a', 'z', Key);

The problem is the inner for loop

for (h = 0; h < strl; h++){
    for (p = 0; p < 26; p++)
    if (text[h] == replace[p])
    text[h] = new[p];}

For example if text[h] is equal to replace[p] then the character text[h] is changed and the inner loop continues its iterations with the new value of text[h] And the new value of text[h] can be again found in the string replace.

At least you need to insert a break statement

for (h = 0; h < strl; h++){
    for (p = 0; p < 26; p++)
    { 
        if (text[h] == replace[p])
        {
            text[h] = new[p];
            break;
        }
    }
}

You could use the standard function strchr instead of writing manually the inner for loop. For example

string replace_char( string text, string replace, string new )
{
    for ( string p = text; *p != '\0'; ++p )
    {
        char *target = strchr( replace, *p );
        if ( target != NULL ) *p = new[target - replace];
    }

    return text;
}

Pay attention to that you need to guarantee that lengths of the strings replace and new are equal each other. Otherwise the function will look more complicated.

@Ted Lyngmo provided the right answer: "need to break out of the inner for() loop"

Below is an annotated revision of your code (for your study.)

// list header files from "C general" to "program specific"
#include <stdio.h>
#include <string.h>
#include <cs50.h>

// a function defined is a function declared.
// no need to prototype if function definition is ahead of its use in main()
void replace_char( string text, string replace, string newvals ) {
    int h;
    for( h = 0; text[ h ]; h++ ) { // no need to measure. bump into the end

        int p; // declare variables when they are needed

        for( p = 0; replace[ p ]; p++ ) { // 'replace' may not be exactly 26 chars

            if( text[ h ] == replace[ p ] ) {

                // this is called "print debugging"... it is useful sometimes
                printf( "char #%d replacing %c with %c\n", h, text[ h ], newvals[ p ] );

                text[ h ] = newvals[ p ];
                // break; // break out of inner loop and move on to next msg character
            }
        }
    }
}

int main() {
    string message = get_string("Type message: ");
    string Alpha = "abcdefghijklmnopqrstuvwxyz";
    string Key  =  "qwertyuiopasdfghjklzxcvbnm";

    replace_char( message, Alpha, Key );

    puts( message ); // alternative function to print str with LF too...

    return 0;
}

Commenting out the break statement that should have been present, that print statement shows what was happening:

Type message: hello there
char #0 replacing h with i
char #0 replacing i with o
char #0 replacing o with g
char #1 replacing e with t
char #1 replacing t with z
char #1 replacing z with m
char #2 replacing l with s
char #2 replacing s with l
char #3 replacing l with s
char #3 replacing s with l
char #4 replacing o with g
char #6 replacing t with z
char #6 replacing z with m
char #7 replacing h with i
char #7 replacing i with o
char #7 replacing o with g
char #8 replacing e with t
char #8 replacing t with z
char #8 replacing z with m
char #9 replacing r with k
char #10 replacing e with t
char #10 replacing t with z
char #10 replacing z with m
gmllg mgmkm

You can add (temporarily) as many print statements as you need so that the program reports what it is doing. It's a good way to find bugs before you start to learn about debuggers.